[알고리즘] 최소 신장 트리(MST) - Kruskal, Prim 알고리즘

0. 최소 신장 트리(MST)

신장 트리
n개의 정점으로 이루어진 무향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리

최소 신장 트리 (MST, Minimum Spanning Tree)
무향 가중치 그래프에서 신장 트리를 구성하는 간선들의 가중치의 합이 최소인 신장 트리

 

최소 신장 트리를 구하는 대표적인 알고리즘인 Kruskal과 Prim에 대해 알아보자.

---

1. Kruskal 알고리즘

크루스칼 알고리즘은 간선 중심 그래프이며, 그리디 알고리즘이다.

1-1. 알고리즘

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

1. 모든 간선을 가중치에 따라 오름차순으로 정렬
2. 가중치가 가장 낮은 간선부터 선택하면서 트리를 증가시킴
   • 사이클이 발생하면 MST에 포함시키지 않음
   • 사이클이 발생하지 않는 경우 MST에 포함
3. n-1개의 간선이 선택될 때까지 2번 반복

1-2. 구현

간선 중심 그래프이기에 간선 리스트로 구현했다.

---

2. Prim

프림 알고리즘은 정점 중심 그래프이며, 그리디 알고리즘이다.

2-1. 알고리즘

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

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

• 2개의 서로소 집합 정보를 유지해야 한다.
  • 트리 정점들(tree vertices) -  MST를 만들기 위해 선택된 정점들
  • 비트리 정점들(non-tree vertices) - 선택되지 않은 정점들

2-2. 구현

정점 중심 그래프이기에 인접 리스트로 구현했다.