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

크루스칼 알고리즘(Kruskal Algorithm)이란 무방향의 가중치 그래프의 모든 정점을 최소 가중치로 연결하는 방법을 의미한다.

최소 스패닝 트리를 찾을 때 대표적으로 사용하는 알고리즘이다. 크루스칼 알고리즘은 무언가를 결정해야 할 때마다 그 순간에

가장 좋다고 생각하는 것을 선택하는 탐욕적인(Greedy) 방법을 따른다. 구체적인 동작 과정은 아래와 같다.

 

1) 모든 엣지들을 끊어 놓는다.
2) 엣지들을 가중치 순으로 오름차순 정렬한다.
3) 정렬된 엣지들을 순서대로 선택한다(가장 낮은 가중치를 먼저 선택).
4) 선택한 엣지가 사이클을 형성하지 않는지 확인한다.
5) 사이클을 형성하지 않는다면, 해당 엣지를 최소 스패닝 트리에 포함시킨다. 

 

모든 엣지들을 끊어 놓는다.

 

엣지들을 가중치 순으로 오름차순 정렬한다.
B-C	D-E	A-C	C-D	D-F	C-E	B-D	E-F
2	2	3	3	3	4	5	5

 

정렬된 엣지들을 순서대로 선택한다.

 

최소 스패닝 트리(엣지 총합 : 2)

[B-C]

 

선택한 엣지가 사이클을 형성하지 않는지 확인한다. 

 

최소 스패닝 트리(엣지 총합 : 4)

[B-C] - [D-E]

 

 

최소 스패닝 트리(엣지 총합 :7)

[B-C] - [D-E] - [A-C]

 

 

최소 스패닝 트리(엣지 총합 : 10)

[B-C] - [D-E] - [A-C] - [C-D]

 

 

최소 스패닝 트리(엣지 총합 : 13)

[B-C] - [D-E] - [A-C] - [C-D] - [D-F]

 

위 그림에서는 엣지를 선택할 때 시 최소 가중치를 선택하면 자연스럽게 사이클이 형성되지 않았다.

그러나 엣지의 가중치가 최소이면서 동시에 사이클을 형성하는 경우도 있다.

따라서 사이클을 형성 여부를 확인하는 과정이 반드시 필요하며, 사이클을 형성하는 경우 해당 엣지는 선택하지 않아야 한다.