최소 스패닝 트리 (MST, Minimum Spanning Tree)

트리(Tree)

• 그래프의 특수한 경우.
• 사이클이 없이 모든 정점이 연결되어 있는 그래프.
• 2개의 노드 사이에 반드시 1개의 간선만을 가짐.
• 부모-자식 관계가 존재하여 계층형 모델이라고도 함. 최상위에 Root 노드 존재.

 

스패닝 트리(Spanning Tree)

• 그래프 내의 모든 정점을 포함하는 트리
• 그래프의 최소 연결 그래프. 
  그러므로 간선의 개수는 (V-1)개 (V는 정점의 개수)
• 스패닝 트리 = 신장 트리

 

최소 스패닝 트리(MST, Minimum Spanning Tree)

• 스패닝 트리 중 간선 가중치의 합이 최소가 되는 스패닝 트리
• MST를 구하는 알고리즘은 보통 아래의 2가지를 많이 사용
  • 크루스칼 알고리즘 (Kruskal Algorithm)
  • 프림 알고리즘 (Prim Algorithm)

 

크루스칼 알고리즘 (Kruskal Algorithm)

• 선택되지 않은 간선 중 최소 가중치를 갖는 간선을 선택해가며 MST를 만드는 알고리즘
• 그리디 알고리즘
• 간선 선택을 기반으로 하는 알고리즘
• 이전 단계에서 만들어진 신장 트리와는 상관없이 무조건 최소 간선만을 선택
• 동작 원리
  1. 간선들의 가중치를 오름차순 정렬
  2. 선택되지 않은 간선 중 최소 가중치를 갖는 간선 선택
  3. 이 간선을 선택했을 때 사이클이 발생한다면 선택하지 않음. 사이클이 발생하는지 확인하는데에는 Union-find 알고리즘 이용.
  4. 총 (V-1)개의 간선이 선택될 때까지 반복.
• 시간 복잡도 : $O(Elog_2E)$
  Union-find 알고리즘은 시간복잡도가 $O(1)$, 즉 상수 시간 복잡도를 가지므로 모든 간선 E개을 오름차순 정렬하는데 걸리는 시간인 $O(ElogE)가 전체 시간 복잡도를 결정하게 된다.

 

프림 알고리즘 (Prim Algorithm)

• 한 정점에서 시작하여 스패닝 트리 집합을 단계적으로 확장해나가는 방법
• 정점 선택을 기반으로 하는 알고리즘
• 이전 단계에서 만들어진 신장 트리를 확장하는 방법
• 프림 알고리즘은 항상 이전 단계에서 만들어진 신장 트리 집합 밖에 있는 정점을 선택하기 때문에 사이클을 형성하지 않는다. 
• 동작 원리
  1. 임의의 시작 정점을 선택하여 MST 집합에 포함
  2. MST 집합에 포함된 정점들에 인접한 정점들 중 최소 가중치를 갖는 정점을 선택.
  3. 총 (V-1)개의 간선이 선택될 때까지 2번 과정을 반복
• 시간 복잡도 : $O(V^2)$
  매번 V개의 정점이 V개의 정점에 대해 탐색을 진행하기 때문이다.
• 최소 힙을 사용하는 경우 시간 복잡도 : $O(ElogV)$
  최소 가중치를 갖는 정점을 선택할 때 그냥 배열이 아닌 최소 힙을 사용하면 시간 복잡도를 줄일 수 있다.

 

크루스칼 vs 프림

크루스칼의 시간 복잡도는 $O(Elog_2E)$, 프림의 시간 복잡도는 $O(ElogV)$이다.

그러므로 그래프 내의 간선이 적은 Sparse Graph는 크루스칼, 간선이 많은 Dense Graph는 프림이 유리하다.

 

[참고]

https://gmlwjd9405.github.io/2018/08/28/algorithm-mst.html#google_vignette

https://velog.io/@nayoon-kim/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EC%B5%9C%EC%86%8C-%EC%8A%A4%ED%8C%A8%EB%8B%9D-%ED%8A%B8%EB%A6%AC