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

크루스칼 알고리즘은 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘.

 

예를 들어, 여러개의 도시가 있을 경우 가장 적은 가중치를 가지는 도시를 먼저 연결한다. 이걸 계속 반복해 나아가며 결국에는 모든 노드를 연결해 그래프를 완성해 나가는 것이다.

 

최종적으로 완성되는 그래프의 간선 숫자는

노드 숫자 == 노드 숫자 - 1

 

"간선을 거리가 짧은 순서대로 그래프에 포함시킨다."

 

 

1. 노드들의 가중치를 오름차순으로 정렬을 수행한다.

2. 정렬된 순서에 맞게 그래프에 포함시킨다.

3. 하지만, 사이클이 형성되는지 확인하고 발생하지 않는 경우에만 간선에 포함시킨다. (사이클 테이블)

 

사이클이란?

좌측은 사이클 형성 x / 우측은 사이클 형성 o

코드 추가 예정.