최소 신장 트리(그래프) // Minimum Spanning Tree(Prim Algorithm, Kruskal Algorithm)

1. Minimum Spanning Tree : 각 간선이 갖고 있는 가중치의 합이 최소가 되는 신장 트리가 바로 최소 신장 트리이다.

 

- Prim Algorithm

1) 그래프와 최소 신장 트리를 준비한다. 이때 최소 신장 트리는 노드가 하나도 없는 상태이다.

2) 그래프에서 임의의 정점을 시작 정점으로 선택하여 최소 신장 트리의 루트 노드로 삽입한다.

3) 최소 신장 트리에 삽입되어 있는 정점들과 이 정점들의 모든 인접 정점 사이에 있는 간선의 가중치를 조사한다.

간선 중에 가장 가중치가 작은 것을 골라 이 간선에 연결되어 있는 인접 정점을 최소 신장 트리에 삽입한다.

단, 새로 삽입되는 정점은 최소 신장 트리에 삽입 되어있는 기준의 노드들과 사이클을 형성해서는 안된다.

4) 3)의 과정을 반복하다가 최소 신장 트리가 그래프의 모든 정점을 연결하게 되면 알고리즘을 종료한다.

 

첫 번째 문제는 최소 신장 트리의 자료구조로 무엇을 사용할 것인가?

-> 최소 신장 트리는 그래프이므로 그래프를 사용하는것도 나쁘지 않다.

두번재 문제는 조사 대상 간선에서 최소 가중치를 가진 녀석을 골라내는 과정에서 발생하는 성능문제

-> '정점이 추가될 때마다 조사 대상 간선 정렬하기'와 '이진 탐색 트리에 조사 대상 간선 입력하기'를 생각해볼 수 있지만, 삽입 삭제가 빠르고 최소 값을 찾는 데에 거의 비용이 들지 않는 우선순위 큐를 이용하는 것이 가장 적절하다.

 

- Kruskal Algorithm

:Prim Algorithm이 최소 신장 트리에 연결된 정점들의 주변의 정보를 파악하여 최소 신장 트리를 완성해나가는 반면, Kruskal Algorithm은 그래프 내의 모든 간선들의 가중치 정보를 사전에 파악하고 이 정보를 토대로 최소 신장 트리를 구축해 나가는것이 특징이다.

 

1) 그래프 내의 모든 간선을 가중치의 오름차순으로 목록을 만듭니다.

2) 1)에서 만든 간선의 목록을 차례대로 순회하면서 간선을 최소 신장 트리에 추가

단, 이때 추가된 간선으로 인해 최소 신장 트리 내에 사이클이 형성되면 안된다.

 

첫 번째 문제는 최소 신장 트리에 생기는 사이클을 어떻게 효율적으로 감지할 것인가?이다.

-> 깊이 우선 탐색을 수행할 때 이미 방문했던 노드를 또 만난다면 사이클이 있다는 뜻이다.

-> 이 알고리즘은 탐색 비용이 크다.

-> 대안으로는 사용 가능한 사이클 탐지방법으로 분리 집합을 이용하는 것이다.