MST(Minimum Spanning Tree) 크루스칼(Kruskal) 알고리즘, 프림(Prim)알고리즘

제129회 예상문제(토픽)

 

정보관리 117회 3교시
3. MST(Minimum Spanning Tree)를 구하는 알고리즘인 크루스칼(Kruskal) 알고리즘, 프림(Prim)알고리즘을 설명하시오

 

문3) MST(Minimum Spanning Tree) 크루스칼(Kruskal) 알고리즘, 프림(Prim)알고리즘

답)

I. MST(Minimum Spanning Tree) 개요

- 각 간선에 가중치(비용, 거리, 시간, 교통량 등)가 있는 무방향 그래프 G에서 모든 정점들을 연결하는 가중치의 합이 최소가 되는 신장 트리

- 특징: 모든 정점 연결, 가중치 최소, 간선의 개수 n-1개, cycle 제거

II. 크루스칼(Kruskal) 알고리즘 

가. 크루스칼 알고리즘 개념 

정의	그래프 내의 모든 간선의 가중치 정보를 사전에 파악하고 이 정보를 토대로 최소 신장 트리를 구성하는 알고리즘
시간복잡도	O(nlogn)
생성 절차	1. 그래프 모든 간선을 가중치로 오름차순 정렬 2. 가중치가 가장 작은 간선을 하나의 집합으로 형성후 신장 트리에 추가 3. 다음 가중치의 간선을 선택해서 신장 트리에 추가 4. Cycle 이 존재하는 지 검증 후 Cycle 이면 제외 5. n-1개의 간선이 될때까지 '2~4'를 반복

-사이클 생성여부는 추가하고자 하는 간선의 양끝 정점이 같은 집합에 속해 있는지를 먼저 검사(union-fid 알고리즘 활용)

나. 크루스칼 알고리즘 절차

순서	도식	상세설명
1		- 초기상태 - 간선의 가중치 오름차순으로 정렬 수행
2		AD 와 CE 가 가장 짧은(가중치가 가장 작은) 간선 임의로 AD 선택
3		CE 가 가중치가 5 로서, Cycle 을 생성하지 않는 가장 짧은 간선이므로 CE 선택
4		가중치 6 인 DF 선택
5		다음으로 가장 짧은 간선은 AB 와 BE 인데 임의로 AB 선택 - BD 선택시 ABD 를 연결시키면 Cycle 이 형성되기 때문에 제외
6		- 가중치 7 인 BE 선택 - Cycle 을 형성하는 BC,EF,DE 제외
6		- EG 선택하면 모든 노드들이 연결되므로 알고리즘 수행 종료

- 간선의 개수를 E, 정점의 개수를 V 라고 할때 O(ElogV)의 시간복잡도를 가짐

II. 프림(Prim) 알고리즘

가. 프림알고리즘 개념 

정의	하나의 정점을 시작점으로 Cycle을 생성하지 않는 범위내 최소가중치를 가지는 정점을 하나씩 포함하여 N-1개의 간선까지 확대하는 알고리즘
시간복잡도	O(n^2)
생성 절차	1. 루트정점 선택(임의의 정점 2. 연결 정점 중 최소 간선으로 정점선택 후 신장 트리에 추가  3. 2를 반복하여 부분집합에 정점을 하나씩 추가 4. Cycle 이 존재하는 지 검증 후 Cycle 이면 제외 5. 간선이 N-1이면 종료

- 정점을 기준으로 간선을 선택 후 하나의 집합으로 보고 인접한 정점중 최소 간선을 선택

나. 프림 알고리즘절차

순서	도식	상세설명
1		초기상태  정점 D를 시작점으로 선택
2		- D 와 연결되어 있는 정점을 선택 - A, B, E, F 중 가중치가 가장 작은 A 선택
3		정점 D 또는 A 와 연결되어 있는 간선 중 가중치가 가장 작은 것 선택 - B,E, F 중 가중치가 가장 작은 F 선택
4		정점 D, A, F 와 연결되어 있는 간선 중 가중치가 가장 작은 것 선택 - B 선택
5		정점 D, A, F, B 와 연결되어 있는 간선 중 가중치가 가장 작은 것 E 선택
6		정점 D, A, F, B, E 와 연결되어 있는 간선 중 가중치가 가장 작은 것 C 선택
7		정점 G는 E, F와 연결가능하나 가중치가 작은 정점 E와 연결하면 모든 정점이 연결되어 알고리즘 수행 종료

간선의 개수를 E, 정점의 개수를 V라고 할 때, 이진힙 사용시 O(ElogV)의 시간복잡도를 가지며, 피보나치힙 사용시 O(E+VlogV)의 시간 복잡도를 가짐

 

IV. 크루스칼 알고리즘과 프림 알고리즘 비교

비교항목	크루스칼 알고리즘	프림 알고리즘
핵심개념	- 사전에 가중치 정보 파악하여 오름차순 정렬하여 트리 구성	- 시작점에서 단계적으로 노드를 추가하는 방식으로 트리 구성
시간복잡도	- O(ElogV)	- 이진힙 사용시 :O(ElogV) - 피보나치힙 사용시: O(E+VlogV)
수행기법	- Union-Find	- 서로 소인 2 개(트리정점, 비트리정점)의 집합정보 유지

- MST 는 정보통신, 건설분야 등에서 배선의 최소길이, 최단 통신선로, 가장 짧은 도로구간, 최단 배관길이 구성 등에 사용됨