크루스칼 알고리즘

신장 트리 : 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프

 

 

크루스칼 알고리즘 : 대표적인 최소 신장 트리 알고리즘

 

1. 간선 데이터를 비용에 따라 오름차순으로 정렬한다.

 

2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인한다.

    (1) 사이클이 발생하지 않으면 -> 최소 신장 트리에 포함한다.

    (2) 사이클이 발생하면 -> 최소 신장 트리에 포함하지 않는다.

 

3. 모든 간선에 대하여 2 의 과정을 반복한다.

 

 

 

필요함 함수 : find 연산, union 연산