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

프림 알고리즘과 동일하게 
가중치 갖는 무향 그래프에서 
최소신장트리 MST 를 찾는 알고리즘 임.

크루스칼 알고리즘은 
시작정점 없이!
모든 간선 중 가중치가 제일 작은 간선을 기준하여 연결하는 것이다.
이때 간선을 연결하며, 사이클 판정 연결 판정은 유니온파인드로 하면 된다.

위와 같은 그래프가 있다면,

 

 

가장 작은 가중치를 갖는 간선 중 사이클이 발생하지 않으므로 모두 연결시킨다.
하나씩 연결하는 순서인데 1-4를 연결하던 4-7을 연결하던 순서는 중요하지 않으므로, 연결판정이 가장 중요하다. 여기서는 두 정점 A-B 을 연결한 간선 중 두 정점중 더 낮은 간선을 먼저 연결한다고 하자. 만약 더 낮은 정점 A 가 같다면 B 가 더 낮은 간선을 연결한다고 하자.
 

 

연결을 하게 되면 위와 같고, 아직 모든 연결이 되어 있지 않으므로, 
가중치가 낮은 순서대로 다시 연결과정을 진행한다.

 

 

가중치 2인 간선을 연결하고 ,
그리고 3인 간선을 연결하려고 보니 유니온파인드로 보면 두 정점 간 루트가 같으므로 합칠 수 없다.
가중치 4인 간선또한 동일하므로 합칠 수 없고 
가중치 5인 간선또한 합칠 수 없다.

누구와도 연결이 되지 않은 정점 10번을 연결하는 가중치 6인 간선을 연결할 수 있다. 

 

그리고 동등한 가중치를 갖는 간선을 기준으로 낮은 정점을 기준하여 간선을 연결하므로......
8-9보다 6-9 간선이 앞서므로 연결시킨다. 
이후 8-9 간선은 정점 8, 9 가 같은 루트를 가지기 때문에... 연결할 수 없다.

 

 

마지막 가중치 10인 간선 또한 정점 9, 정점 10이 같은 루트를 가지므로 연결할 수 없다.

 

결과로 프림이나 크루스칼이나 동등한 그래프가 주어질 때  동일한 기준으로 MST를 구하면 같게 나온다.