[알고리즘]MST 최소 신장 트리 알고리즘 - Kruskal & Prim

[ Spanning Tree ]

 

 Spanning Tree(신장 트리)는 그래프 내의 모든 정점을 포함하는 트리입니다. 

 

 그래프의 n 개의 정점을 모두 연결하는 최소 간선의 수는 (n-1) 개이고, 이때 이루어진 그래프를 최소 연결 부분 그래프, 즉 Spanning Tree라고 합니다.

 

 즉, 그래프에서 일부 간선을 선택해서 만든 트리입니다. 

 

 -  Spanning Tree 특징

• DFS, BFS를 이용하여 그래프의 신장 트리를 찾을 수 있다.
• 하나의 그래프에는 많은 신장 트리가 존재할 수 있다. 
• 신장 트리는 모든 정점들이 연결되어 있어야 한다. 
• 신장 트리는 사이클을 포함해서는 안된다. 
• 신장 트리는 n 개의 정점과 (n-1) 개의 간선으로 이루어져 있다. 

 

 

 

 

[ MST 최소 신장 트리 ]

 

 최소 신장 트리(MST, minimum spanning tree)는 Spanning Tree 중에서 간선들의 가중치 합이 최소인 트리입니다. 

 

 즉, 그래프의 모든 정점을 연결한 그래프 중 연결된 간선의 가중치 합이 최소인 신장 트리입니다. 

 

 

 -  MST 특징

• 간선의 가중치 합이 최소
• n 개의 정점과 (n-1) 개의 간선
• 사이클이 포함되선 안됨

 

 MST 를 구현하는 알고리즘에는 Kruskal MST 알고리즘과 Prim MST 알고리즘이 있습니다. 

 

 

 

 

 

[ Kruskal MST 알고리즘 ]

 

 Kruskal MST 알고리즘은 그리디 알고리즘을 이용하여 그래프의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 알고리즘입니다. 

 

 간선 선택을 기반으로 하는 알고리즘입니다. 

 

- 알고리즘

1. 그래프의 간선들을 가중치의 오름차순으로 정렬 -> 최소 힙으로 구현

2. 각 정점은 자기 자신만을 정점으로 갖는 트리를 구성한다. 

   - 각 정점의 root 정점은 자기 자신으로 초기화

3. 최소 힙(간선 리스트)에서 첫 번째 간선(가중치가 최소인)을 pop

4. 해당 간선이 사이클을 발생시키는지 확인

   - 해당 간선에 양 끝 정점의 root 정점을 찾는다.(find)

   - 두 root 정점이 갖다면, 사이클을 발생시키므로 2단계로 돌아간다. 

   - 두 root 정점이 다르다면, 한 정점의 root 정점을 다른 한 정점의 root 정점으로 갱신한다.(union)

5. 최소 신장 트리에 해당 간선의 정보 추가

6. 최소 힙(간선 리스트)가 empty일 때까지 3~5 과정 반복

 

 

 

 

[ Prim MST 알고리즘 ]

 

Prim MST 알고리즘은 시작 정점에서부터 출발하여 신장트리 집합을 단계적으로 확장 해나가는 방법입니다. 

 

정점 선택을 기반으로 하는 알고리즘으로 BFS와 유사합니다.

 

 

- 알고리즘

1. 시작 정점을 MST 에 추가한다. 

2. 시작 정점에 대한 정보를 최소 힙(우선순위큐)에 추가한다. (가중치 오름차순)

   - 최소 힙: MST 를 찾을 자료구조

3. 힙에서 정점을 pop 한다. 

4. 해당 정점이 이미 방문한 정점이라면 3단계로 돌아간다. 

5. 방문하지 않은 정점이라면, MST 에 해당 정점의 정보를 추가한다. 

6. 방문 표시 후 해당 정점에 연결된 정점과 그 가중치를 최소 힙에 추가한다. 

7. 최소 힙이 empty 일 때까지 3~6 과정을 반복한다.