[그래프] 최소 신장 트리 - Prim, Kruskal Algorithm

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

그래프에서 모든 정점에 대해 최소한의 연결만을 남긴 그래프이다. 즉, 간선의 가중치 합이 가장 작은 트리를 뜻한다.

사이클이 존재하지 않아야 한다.

 

 

최소 신장 트리를 찾는 알고리즘으로는 다음과 같이 두 가지가 있다.

1. Prim 알고리즘
2. Kruskal 알고리즘

 

 

Prim 알고리즘

프림 알고리즘은 아래의 방법을 반복한다. 단, 아래 과정을 반복하는 과정에서 사이클이 형성되지 않아야 한다.

1. 임의의 정점을 선택하여 하나의 정점을 가지는 최초의 트리를 구성한다. 
2. 트리에 포함된 정점과 트리에 포함되지 않은 정점 간의 간선 중, 가장 가중치가 적은 간선을 선택하여 트리에 추가한다.
3. 모든 정점이 트리에 포함될 때까지 2를 반복한다.

 

예시1)

 

최종 신장 트리

 

 

예시2)

 

 

 

Kruskal 알고리즘

 

프림 알고리즘은 노드를 선택하고 선택된 노드들과 연결된 에지들의 가중치를 비교하였다. 이와 달리, 크루스칼 알고리즘은 에지 자체의 가중치를 바로 비교하는 알고리즘이다. 

 

크루스칼 알고리즘은 에지들을 가중치에 따라 오름차순으로 정렬한 뒤, 가중치가 작은 에지부터 최소 신장 트리에 추가한다. 도중에 사이클이 발생할 경우, 가장 가중치가 큰 에지를 뺀다.

 

 

크루스칼 알고리즘은 아래의 방법을 반복한다. 단, 아래 과정을 반복하는 과정에서 사이클이 형성되지 않아야 한다.

1. 모든 간선들의 가중치를 오름차순으로 정렬한다.
2. 가중치가 가장 작은 간선을 선택한다.
3. 위에서 선택한 간선이 연결하려는 2개의 노드가 서로 연결되지 않은 상태라면, 2개의 노드를 서로 연결한다.
4. 이 과정을 반복해서 최소 신장 트리를 완성한다.

 

예시1)

 

 

 

 

예시2) 

사이클 방지 위해 9 선택

최종 신장 트리

 

 

 

 

---

Reference

 

https://growth-coder.tistory.com/40

[Algorithm] 프림 알고리즘(Prim algorithm)과 크루스칼 알고리즘 (Kruskal algorithm)

https://memodayoungee.tistory.com/107#%ED%81%AC%EB%A3%A8%EC%8A%A4%EC%B9%BC%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98(Kruskal%C2%A0Algorithm)-1

[알고리즘] 최소 신장 트리 - Prim, Kruskal Algorithm(프림, 크루스칼 알고리즘)