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

다음과 같은 그래프가 있다고 해보자.

신장 트리는 그래프의 부분적인 트리라고 볼 수 있는데 그래프의 모든 노드를 갖고 있지만 에지의 경우 사이클이 생기지 않는 최소 부분만 가지고 있는 트리이다.

 

위의 그래프의 신장 트리는 여러 경우의 수가 존재한다. 많기 때문에 일부만 소개한다.

최소 신장 트리란 가중 그래프의 신장 트리 중에서 가장 가중치의 합이 작은 트리를 의미한다.

 

이렇나 최소 신장 트리를 구하는 방법인 Prim's algorithm과 Kruskal's algorithm에 대해서 공부해보려 한다.

 

 

Prim algorithm

1. 노드 하나를 선택한다.
2. 선택된 노드들과 이어진 노드들 중 가장 가중치가 적은 노드를 고른다.
3. 지금까지 선택된 노드들과 연결된 노드들 중 가장 가중치가 적은 노드를 고른다.

위 방법을 반복하는 것이 프림 알고리즘이다.

 

위 그래프의 노드 A부터 시작하여 최소 신장 트리를 구해보려한다.

A에서 갈 수 있는 곳은 B와 C이고 가장 작은 가중치는 5이므로 C를 최소신장 트리에 추가한다.

 

계속 진행해본다면

이번엔 A와 연결된 B, C와 연결된 B, E, D를 조사한다.

 

6이 가장 작으므로 D를 최소 신장 트리에 추가한다.

 

 

최종 신장 트리

Kruskal algorithm

프림 알고리즘은 노드를 선택하고 선택된 노드들과 연결된 에지들의 가중치를 비교하였다.

 

크루스칼 알고리즘은 에지 자체의 가중치를 바로 비교하는 알고리즘이다.

 

크루스칼 알고리즘은 에지들을 가중치에 따라 오름차순으로 정렬을 한 뒤가중치가 작은 에지부터 최소 신장 트리에 추가하는 알고리즘이다.

 

물론 사이클이 생겨선 안된다. 사이클이 발생할 경우 가장 가중치가 큰 에지를 빼면된다.

 

다음 그래프로 크루스칼 알고리즘을 적용해보겠다.

최종 최소 신장 트리