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

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

최소 신장 트리를 만들기 위한 알고리즘이다.

1. 모든 간선들을 오름차순으로 정렬한다.

2. 가중치가 가장 적은 간선을 추가한다.

3. 추가된 간선이 사이클을 만들면 삭제한다.

 

2~3번의 동작을 반복한다.

 

시간복잡도: O(m log m)