Prim's Algorithm은 가중치가 있는 무방향 Connected Graph에서 Minimum Spanning Tree를 만듭니다.
목표는 Source에서의 최단 거리가 아니라 모든 Vertex를 연결하는 Edge의 총 Weight를 최소화하는 것입니다.
핵심 아이디어
하나의 Vertex에서 시작해 현재 Tree와 아직 방문하지 않은 Vertex를 잇는 가장 저렴한 Edge를 계속 선택합니다.
Cut Property
Prim의 정당성은 Cut Property에 기반합니다.
현재 Tree와 나머지 Vertex 사이를 가르는 Cut에서 가장 가벼운 Edge는 MST에 포함될 수 있습니다.
Prim vs Kruskal
Prim은 하나의 Tree를 확장합니다.
Kruskal은 모든 Edge를 정렬하고 Union-Find로 Cycle을 막습니다.
Prim vs Dijkstra
Prim:
Code
최소 전체 Tree 비용Dijkstra:
Code
Source에서 각 Vertex까지 최단 거리음수 Weight
MST에서는 Negative Edge도 사용할 수 있습니다.
Disconnected Graph
전체 MST는 존재하지 않고 Minimum Spanning Forest를 만들어야 합니다.
활용
- Fiber Network
- Cable Layout
- Data Center Backbone
- Sensor Network
- Utility Network
복잡도
Heap + Adjacency List:
Code
O(E log V)Matrix:
Code
O(V²)정리
모든 Vertex를 최소 총비용으로 연결해야 하는 Weighted Undirected Graph 문제에서 Prim이 핵심 선택지입니다.