[알고리즘/MST] 최소 신장 트리 (Minimum Spanning Tree)

Spanning Tree

---

 

• 그래프 내의 모든 정점을 포함하는 트리
• 그래프의 최소 연결 부분 그래프
  
  • 최소 연결 = 간선의 수가 가장 적음
  • 정점이 n개 일 때, 그래프의 최소 간선 수 = n-1, n-1개의 간선으로 연결되어 있으면 트리형태가 되고 이게 스패닝 트리
  • 즉 , 그래프 일부 간선을 선택해서 만든 트리
• 모든 정점들이 연결 되어 있어야함
• 사이클을 포함해서는 안됨

 

 

 

MST (Minimum Spanning Tree)

---

• Spanning Tree 중에서 사용된 간선들의 가중치 합이 최소인 트리
  • 간선의 가중치의 합이 최소여야함
  • n개의 정점을 가지는 그래프에서 반드시 n-1개만의 간선을 사용해야함
  • 사이클에 포함되어서는 안됨

 

 

 

MST 구현 방법

---

1. Kruskal 알고리즘

---

• 탐욕적인 방법 (Greedy method)를 이용
  • 결정을 해야할 때 마다 그 순간에 가장 좋다고 생각되는 것을 선택함으로써 최종적인 해답에 도달하는 것
• 각 단계에서 사이클을 이루지 않는 최소 비용 간선을 선택
  • "최소 비용의 간선으로 구성, 사이클을 포함하지 않음" 이라는 MST의 조건에 근거
• 간선 중심 알고리즘 (간선리스트 활용)

 

1-1. Kruskal 알고리즘 동작

---

1. 그래프의 간선들을 가중치의 오름차순으로 정렬

2. 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선 선택

    -> 가중치가 가장 낮은 것부터 선택. 단, 사이클을 형성하는 간선은 제외

    -> 사이클 형성 유무 체크 시, Union-find 활용 (union 성공 시 싸이클 형성X, 실패 시 싸이클 형성O)

3. 해당 간선을 최소 비용 신장 트리의 집합에 추가

 

 

1-2. Kruskal 알고리즘 시간 복잡도

---

• 간선들을 정렬하는 시간에 좌우 됨
  • 간선 e개를 퀵 정렬과 같은 효율적인 알고리즘으로 정렬한다면  O(elog2e) 2는 밑임... 서식 GG... 
  • 그래프의 간선이 적다면 (희소 그래프라면) Kruskal 알고리즘이 적합

 

---

2. Prim 알고리즘

---

 

• 시작 정점에서부터 출발하여 신장트리 집합을 단계적으로 확장해나가는 방법
• 정점 중심 알고리즘 (인접 행렬, 인접 리스트 활용)
• 이전 단계에서 만들어진 신장 트리를 확장하는 방법

 

2-1. Prim 알고리즘 동작

---

1. 처음에는 시작 정점만이 최소 비용 신장 트리 집합에 포함됨

  -> 임의의 정점을 시작점으로 하여 시작

2. 앞단계에서 만들어진 MST 집합에 인접한 정점들 중에서 최소 간선으로 연결된 정점을 선택하여 트리 확장

  -> 가중치 낮은 것부터 먼저 선택

3. 위의 과정을 트리가 n-1개의 간선을 가질 때까지 반복

 

2-2. Prim 알고리즘 시간 복잡도

---

• 주 반복문이 정점 수 N만큼 반복, 내부 반복문이 N번 반복
  • 즉, O(n^2)
  • 그래프에 간선이 많이 존재하는 경우 (밀집 그래프인 경우) 적합

 

 

 

 

 

 

----- 참고 글 -----

gmlwjd9405.github.io/2018/08/28/algorithm-mst.html

[알고리즘] 최소 신장 트리(MST, Minimum Spanning Tree)란 - Heee's Development Blog

gmlwjd9405.github.io/2018/08/29/algorithm-kruskal-mst.htmlhttps://gmlwjd9405.github.io/2018/08/29/algorithm-kruskal-mst.html

[알고리즘] Kruskal 알고리즘 이란 - Heee's Development Blog