Kruskal Algorithm

Kruskal Algorithm

  : 그리디 방법을 사용하여 그래프의 모든 정점을 최소 비용으로 연결하는 최적 해답을 구하는 것

 

• 각 단계에서 사이클을 이루지 않는 최소 비용 간선을 선택
• 간선 선택을 기반으로 하는 알고리즘
• 이전 단계에서 만들어진 신장 트리와 무관하게 무조건 최소 비용 간선 선택

 

 

• Kruskal 알고리즘 과정

1. 그래프의 간선들을 가중치를 기준으로 오름차순 정렬
2. 정렬된 간선 리스트에서 순서대로 사이클을 형성하지 않는 간선 선택 -> 최소 가중치 먼저 선택, 사이클 형성하는 간선은 제외
3. 해당 간선을 현재의 MST 집합에 추가

 

 

• Kruskal 알고리즘 예

출처 : https://gmlwjd9405.github.io/2018/08/29/algorithm-kruskal-mst.html

주의할 점

 

! 간선을 선택할 때 사이클을 생성하는지 확인

   => 추가할 간선의 양 정점이 같은 집합에 속하면 안 된다.

 

사이클 생성 여부 확인 방법

: 추가할 간선의 양 정점이 같은 집합에 속해 있는지 확인

 (using ‘union-find 알고리즘’)

kruskal 알고리즘 로직

 

• Kruskal 알고리즘 시간 복잡도

Union-find 알고리즘 이용

-> Kruskal 알고리즘의 시간 복잡도는 간선 정렬 시간에 의해 좌우된다.

 

간선 m개를 효율적인 알고리즘(ex. 퀵 정렬)으로 정렬한다면

: O(m log m)

 

while문

: 거의 O(m) (간선에 대해서 반복문 돌림)

 

 

=> 전체 수행시간 : O(m log m)

 

 

간선이 적은 희소 그래프(Sparse Graph)에 적합

 

 

 

참고 : HUFS 알고리즘 강의자료,

https://gmlwjd9405.github.io/2018/08/29/algorithm-kruskal-mst.html