최소 스패닝 트리(MST, Minimum Spanning Tree); 프림, 크루스칼 알고리즘

스패닝 트리 (Spanning Tree)

-> 연결 그래프 G의 스패닝(신장) 트리란, G의 모든 정점을 포함하는 부분 그래프로서의 트리. 모든 정점들이 연결되어 있어야 하며 사이클이 존재해서는 안 됨. n개의 정점을 갖는 스패닝 트리는 반드시 n-1개의 에지를 가짐.

 

 

 

최소 스패닝 트리(최소 신장 트리)

-> 가중치 그래프의 스패닝 트리들 중에서 에지들의 가중치 합이 최소인 스패닝 트리.

 

연결그래프 G의 스패닝 트리 a,b,c,d 중 최소 스패닝 트리는 c이다.

 

 

 

▷ Prim의 MST 알고리즘

 

 

○ 아이디어

: 스패닝 트리 집합의 인접 정점 중 최소 가중치로 연결된 정점을 추가하며 스패닝 트리 집합을 점진적으로 확장해 나가자!

 

 

 

 

 

○ 알고리즘

 

1. 임의의 시작 정점에서 출발. (대개 인덱스가 가장 작은 정점) 시작 정점을 스패닝 트리 집합(MST)에 추가.

2. MST에 인접한 정점 중에서 최소 가중치로 연결된 정점을 선택하여 MST에 추가

3. MST가 n-1개의 에지를 가질 때까지 2번을 반복.

 

 

 

 

a 정점을 시작 정점으로 하는 prim 알고리즘 예시

 

 

○ 시간 복잡도

: O(n²), 정점 수에 비해 에지가 많은 경우에 효율적.

 

 

 

 

 

 

▷ Kruskal의 MST 알고리즘

 

 

○ 아이디어

: 가중치 값이 작은 에지들부터 하나씩 추가해서 가중치 합이 최소가 되도록 만들자!

 

 

 

 

 

○ 알고리즘

 

1. 그래프 G에 남아있는 에지들 중에서 최소 가중치를 갖는 에지 선택

2. 선택한 에지가 스패닝 트리 집합(MST)에 속한 에지들과 사이클을 형성하면 선택 취소

3. 선택한 에지 수가 n-1개가 될 때까지 1,2번 반복

 

 

v1을 시작 정점으로 하는 크루스칼 알고리즘 예시

 

 

○ 시간 복잡도

: O(mlogm), 정점에 비해 에지 수가 적은 그래프일 때 효율적.