개요
Kruskal's Algorithm 과 같이 최소신장 트리를 구하는 또다른 방법.
Dijkstra's Algorithm 이랑 코드 흐름이 유사한 부분이 있다.
집합 Y에서 집합 V-Y를 연결하는 가장 낮은비용의 edge를 포함시켜나가는 방법이다.
High-level Algorithm
F = {}; // 최소신장 트리
Y = {v1}; // 집합 Y. 처음에는 v1만 포함되어있다.
While (the instance is not solved)
{
select a vertex in V-Y that is nearest to Y;
add the vertex to Y;
add the edge to F;
if (Y==V)
the instance is solved;
}
Prim's Algorithm
W[i][j] : 초기 edge cost가 기록된 adjcant matrix
- vi에서 vj로의 이음선이 있다면 : 이음선의 가중치
- vi에서 vj로의 이음선이 없다면 : INFINITY
- i == j 라면 : 0
nearest[i] : Y에 속한 정점 중에서 vi에서 가장 가까운 정점의 인덱스 (트리를 거슬러 올라가는 parent이기도 함)
distance[i] : vi와 nearest[i]를 잇는 이음선의 가중치
// n : vertex의 개수
// W[i][j] : edge cost
// F : 반환용 최소신장트리
void prim(int n, const number W[][], set_of_edges& F)
{
index i; // 루프용 index
index vnear; // vnear : 현재 선택된 가장 가까운 V-Y vertex
number min; // 최소비용 vertex를 구하기 위한 거리비교변수
edge e; // edge 임시변수
index nearest[2..n]; // Y에 속한 정점 중에서 vi에서 가장 가까운 정점의 인덱스
number distance[2..n]; // vi와 nearest[i]를 잇는 이음선의 가중치
F = {}; // 최소신장트리
for (i = 2; i <= n; i++) // 초기화
{
nearest[i] = 1; // vi들의 가장 가까운 Y점은 v1이다.
distance[i] = W[1][i]; // vi들의 nearest[i]와 거리를 실제 거리로 초기설정.
}
repeat(n-1 times)
{
min = INFINITE;
for (i = 2; i <= n; i++) // vnear 찾기
{
if (0 <= distance[i] <= min) // 방문한곳(-1)을 제외하고 가장 가까운 지점을 찾는다.
{
min = distance[i];
vnear = i;
}
}
e = edge connecting vertices indexed by vnear and nearest[vnear];
add e to F;
distance[vnear] = -1; // vnear는 Y에 편입되었다.
for (i = 2; i <= n; i++) // 선택된 vnear에 대해서 연결된 vertex의 nearest와 distance 갱신
{
if (W[vnear][i] < distance[i])
{
distance[i] = W[vnear][i];
nearest[i] = vnear;
}
}
}
}
Complexity
Time-complexity : $O((n-1) * 2(n-1)) = O(n^2)$
우선순위큐를 사용하면 $O(mlogn)$으로 줄일수 있다. (힙을 구성하는 시간복잡도)