CS : Algorithm : 최소 비용 신장 트리(MST)

Spanning Tree (스패닝 트리, 신장 트리)

 

 

1.

그래프 내의 모든 정점을 포함하는 트리

 

2.

최소 연결 = 간선의 수가 가장 적다.

n개의 정점을 가지는 그래프의 최소 간선 수는 (n-1)이고, (n-1)개의 간선으로 연결된 그래프는 필연적으로 스패닝 트리가 된다.

 

3.

하나의 그래프에는 많은 스패닝 트리가 있다.

 

 

 

---

 

 

MST (Minimum Spanning Tree)

 

 

1.

spaniing tree 중, 간선의 가중치의 합이 최소인 트리

 

2.

n개의 정점을 가지는 그래프에 대해서, 반드시 (n-1)개의 간선만 이용해야 한다.

 

3.

구현 종류

• Kruskal MST 알고리즘
• Prim MST 알고리즘

 

 

---

 

Kruskal MST 알고리즘

 

1.

greedy method를 활용하여 모든 정점을 최소의 가중치로 연결하는 방법을 찾는 알고리즘

 

2.

• 그래프의 간선들의 가중치를 기준으로 오름차순 정렬한다.
• 가중치를 선택해 나아가는데, 이 때 사이클이 형성되지 않는 가장 낮은 가중치를 선택한다.
• 반복

 

3.

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

즉, 이전 단계에서 만든 신장 트리와는 관계 없이, 현 단계에서 무조건 최소의 가중치가 되는 간선을 선택한다.

 

 

 

 

---

 

 

Prim MST 알고리즘

 

1.

시작 정점으로부터, 신장 트리 집합을 단계적으로 확장해나가는 방법

 

2.

정점 선택을 기반으로 하는 알고리즘이다.

즉, 이전 단계에서 만든 신장 트리를 기준을 확장하는 방법

 

 

 

 

 

---

 

 

Kruskal과 Prim 비교

 

1.

Kruskal의 시간 복잡도 : O(n^2)

 

2.

Prim의 시간 복잡도 : O(elog2e)

 

3.

간선이 적은 그래프의 경우, Kruskal이 유리하고,

간선이 많은 그래프의 경우, Prim이 유리하다.