[알고리즘] 최소 신장 트리(MST) : 크루스칼 알고리즘

스패닝(신장) 트리

 

스패닝 트리(Spanning Tree)

그래프의 스패닝 트리란, 그래프의 모든 정점을 잇지만 사이클이 없는 부분 그래프입니다.

 

위의 사진처럼 형태와 관계없이 모든 정점을 사이클 없이 이을수만 있다면 스패닝 트리라고 부를 수 있습니다.

 

스패닝 트리는 V개의 모든 정점을 연결하는 간선의 수는 V-1개입니다.

 

 

 

최소 스패닝 트리(MST)

최소 스패닝 트리란 원본 그래프에서 신장 트리를 만들 수 있는 경우의 수들 중 최소의 간선 비용을 들여서 만들 수 있는 신장트리를 최소 신장 트리라고 합니다.

 

위의 그림을 예시로 보면, 빨간색 선으로 이루어진 신장 트리르릴 만드는 데 비용이 13이 듭니다. 이는 위의 그래프에서 합을 구할 수 있는 경우의 수중 가장 적은 비용을 나타냅니다.

 

이렇게 최소 신장 트리를 효율적으로 찾아낼 수 있는 알고리즘 방법론들 중 하나가 크루스칼 알고리즘입니다.

 

 

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

[동작 원리]

• 선택되지 않은 간선들 중 최소 가중치인 간선을 선택한다.
• 만약 그 간선을 선택했을 때, 지금까지 구성된 스패닝 트리에 사이클이 없을 경우에만 선택한다.
• 총 V-1개의 간선이 선택될 때까지 반복한다.

 

1번 과정

우선, 선택되지 않은 간선들 중 최소 간선인 1을 선택합니다. 이 간선을 선택해도 현재까지 구성한 스패닝 트리에 사이클이 발생하지 않으므로, 이를 스패닝 트리에 추가합니다.

 

2번 과정

그다음 최소 가중치를 갖는 간선 2를 선택합니다. 이번에도 사이클이 발생하지 않으므로 스패닝 트리에 추가합니다.

 

3번 과정

다음은 가중치가 3인 간선이 선택되지만, 이 간선을 스패닝 트리에 추가하면 사이클이 발생하기 때문에 이 간선을 선택하지 않습니다.

 

4번 과정

위의 과정을 반복하다보면 위와 같은 결과를 얻을 수 있을 것입니다. 위의 사진의 빨간색 선들이 완성된 스패닝 트리입니다.

 

3번 과정에서 사이클이 발생하는지에 대한 여부를 판단하기 위해 Union-Find 알고리즘을 사용하는데 이 알고리즘과 프림 알고리즘은    아래 포스팅에서 확인할 수 있습니다.

 

 

파이썬 예제 코드