[ 알고리즘 ] 최소 신장 트리(MST) / 프림 알고리즘 (Prim Algorithm)

신장트리(Spanning Tree)란?

방향성이 없는 그래프의 서브그래프(Subgraph)들 중에서 모든 정점을 연결하는 트리를 말한다. 서브그래프는 주어진 그래프에서 일부 정점과 간선만을 택해서 구성한 새로운 트리를 말한다. 신장 트리는 그래프의 하위 개념이기도 하다.

그래프에서 난데없이 트리?

그래프는 사이클을 형성하는 간선만 제거하면 트리로 변신할 수 있다. 

그래프 vs 트리

그래프

- 정점(Vertex)와 그 노드를 연결하는 간선(Edge)으로 이루어져 있다.

 

트리

- 그래프의 일종

- Cycle을 가지지 않는다.

- 계층적 구조를 가진다.

- 단 하나의 root를 가진다.

최소 신장 트리(Minimum Spanning Tree : MST)란?

최소 가중치 신장 트리(Minimum Weight Spanning Tree)라고도 불린다.

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

한 그래프에서 최소 신장 트리는 하나가 아니라 여러개일 수 있다.

 

 

최소신장트리 알고리즘에는 프림 알고리즘, 크루스칼 알고리즘 두가지가 있다.

 

프림 알고리즘은 정점을 추가하면서 트리를 확장하는 방법이고,
크루스칼 알고리즘은 간선을 추가하면서 최소 신장 트리를 만드는 방법이다.

 

프림은 시작점을 정하고, 시작점에서 가까운 정점 + 최소 비용을 선택하면서 MST를 구성하므로 그 과정에서 사이클을 이루지 않는다.

크루스칼은 시작점을 정하지 않고, 최소 비용의 간선을 차례로 대입하면서 MST를 구성하므로, 그 과정에서 사이클이 이뤄지는지 체크해야한다. 사이클을 확인하는 방법으로는 유니온 파인드(Union-Find)방법이 있다.

 

프림 알고리즘

로버트 프림(Robert C. Prim)이 고안한 그래프에서 최소 신장 트리를 만들어내는 알고리즘이다.

 

과정은 다음과 같다.

① 그래프와 최소신장 트리를 준비한다. 물론 최소 신장 트리는 아직 노드가 하나도 없는 상태

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

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

④ 연결된 간선 중에 가장 가중치가 작은 것을 골라, 이 간선에 연결되어 있는 인접 정점을 최소 신장 트리에 삽입한다. 단, 새로 삽입되는 정점은 최소 신장 트리에 삽입되어 있는 기존의 노드들과 사이클을 형성해서는 안된다.

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

주의사항

④과정의 주의사항인 사이클이 생기지 않게 하기 위해

예를 들어, 트리에 삽입된 정점들과 연결된 정점들을 조사할 때, 트리에 삽입된 정점 A와 F가 A-F로 연결되어 있고

A-(20)-C

F-(70)-C

로 연결되어 있다면, A-F-C의 사이클을 형성할 수 있기 때문에 가중치가 더 적은 A-(20)-C 간선을 선택한다.