최소 신장 트리(MST) - 크루스칼 알고리즘 / 프림 알고리즘

신장트리(Spanning Tree)란? 

1. N개의 정점

2. N-1개의 간선

3. 사이클이 존재하지 않는다.

위 3가지 조건을 갖춘 트리를 신장트리라고 한다.

 

최소 신장 트리란? (Minimum Spanning Tree)

무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장트리를 말한다.

 

 

MST 알고리즘 종류

• 크루스칼(Kruskal) - 간선중심
• 프림(Prim) - 정점 중심

따라서, 간선 적으면 크루스칼, 간선 많으면 프림을 사용하면 된다.

 

 

크루스칼 알고리즘

- 간선을 하나씩 선택해서 MST를 찾는 알고리즘

1. 최초, 모든 간선을 가중치에 따라 오름차순으로 정렬
2. 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시
3. 사이클이 존재하면 다음으로 가중치가 낮은 간선 선택 - 사이클 여부 확인을 위해 union-find 알고리즘이 사용된다.
4. n-1 개의 간선이 선택될 때까지 2, 3을 반복

출처 : https://velog.io/@hwi_chance/CS-Algorithm-Part.4-Minimum-Spanning-Tree

 

프림 알고리즘

- 하나의 정점에서 연결된 간선들 중에 하나씩 선택하면서 MST를 만들어 가는 방식

1. 임의 정점을 하나 선택해서 시작
2. 선택한 정점과 인접하는 정점들 중의 최소 비용의 간선이 존재하는 정점을 선택
3. 모든 정점이 선택될 때 까지 1,2 과정을 반복

출처 : https://velog.io/@hwi_chance/CS-Algorithm-Part.4-Minimum-Spanning-Tree

 

정점에서 최단거리를 찾는 게 다익스트라와 비슷하지만,

프림은 dist 배열이 정점 v를 신장트리에 연결하는 최소비용을 위해 사용되는 반면,

다익스트라 알고리즘에서 dist 배열은 정점 r에서 v에 이르는 최단거리를 위해 사용한다.