[Algorithm] 최소신장트리 알고리즘

I. 신장트리 (Spanning Tree)의 개요

가. 신장 트리의 정의

모든 정점을 포함하고 정점 간 서로 연결하면서 사이클이 존재하지 않는 그래프

 

최소신장트리의 정의

정점 간 가중치(cost)의 합이 최소인 신장 트리

 

Ⅱ. 최소신장트리 알고리즘

가. Prim의 알고리즘

 

* 시작점 기반 최소 가중치 * 정점마다 edge 검사 * 우선순위 큐 기반 구현 임의의 vertex를 선택, 신장 트리의 루트 노드로 삽입 선택된 vertex와 인접 vertex들 사이의 edge 가중치 검사 최소 가중치를 가지는 edge를 선택 해당 edge로 두 정점을 연결했을 때, cycle이 발생하면 버리고, 그렇지 않으면 신장트리에 삽입 선택된 edge는 edge리스트에서 제거 edge리스트에 더 이상의 edge가 없을 때까지 2~5번 반복

void prim(int n, const number W[][], set_of_edges& F) { index i, vnear; number min; edge e; index nearest[2..n]; number distance[2..n]; F = empty_set; for(i=2;i <= n;i++) { nearest[i] = 1; distance[i] = W[1][i]; } repeat(n-1 times) { min = ; for(i=2; i <= n; i++) { if 0 <= distance[i] < min) { min = distance[i]; vnear = i; }} e = vnear와 nearest[vnear]를 잇는 이음선; e를 F에 추가; distance[vnear] = -1; for(i=2; i <= n; i++) if (W[i][vnear] < distance[i]) { distance[i] = W[i][vnear]; nearest[i] = vnear; }}}

 

나. Kruskal의 알고리즘

* 가중치의 오름차순 정렬 수행 * 최소 가중치 edge 선택 * 분리집합 기반 구현 그래프 내의 모든 edge을 가중치의 오름차순으로 정렬 현재 edge들 중에서 가중치가 가장 적은 edge를 선택 해당 edge로 두 정점을 연결했을때, cycle이 발생하면 버리고, 그렇지않으면 신장트리에 삽입 선택된 edge는 edge리스트에서 제거 edge리스트에 더 이상의 edge가 없을 때까지 2~3 반복
	⇒
void kruskal( int n, int m, set_of_edges E, set_of_edges& F) { index i, j; set_pointer p, q; edge e; E에 속한 m개의 이음선을 가중치의 비내림차순으로 정렬; F = emptyset; initial(n); while (F에 속한 이음선의 개수가 n-1보다 작다) { e = 아직 점검하지 않은 최소의 가중치를 가진 이음선; i, j = e를 이루는 양쪽 정점의 인덱스; p = find(i); q = find(j); if (!equal(p,q)) { merge(p,q); e를 F에 추가; }}}