최소 신장 트리 구하기 : 크루스칼(Kruskal) 알고리즘

신장 트리(Spanning Tree)

모든 정점을 연결하되, 사이클이 존재하지 않는 그래프

 

위 그래프에서 신장 트리를 찾는다면? 아래와 같이 다양한 신장 트리를 만들 수 있다!!!

원본 그래프의 부분 그래프이므로 여러 개가 생길 수 있다

 

최소 신장 트리(Minimum Spanning Tree, MST)

신장 트리 중에서 간선 가중치의 합이 최소인 것

 

 

사용 사례

- 도시를 모두 연결하는 도로의 비용이 최소가 되는 것을 구하기

- 전화선의 길이가 최소가 되도록 전화 케이블 망을 구성하기

 

 

대표 알고리즘

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

- 프림(Prim) 알고리즘

 

 

크루스칼 알고리즘

- 그래프의 간선들을 가중치의 오름차순으로 정렬한다

- 정렬된 순서대로 간선들을 선택한다

- 사이클이 발생하지 않도록 한다

 

 

동작 과정

(1) 그래프의 간선들을 가중치의 오름차순으로 정렬한다

 

(2) 가중치가 작은 연결부터 선택한다

 

(3) 사이클이 발생하면 선택하지 않는다

 

(왼쪽) 가장 작은 가중치의 간선을 선택했으나 사이클이 발생하므로 pass

(오른쪽) 그 다음으로 작은 가중치의 간선을 선택했을 때 신장 트리가 완성됐다 (모든 노드가 연결되어 있음)

 

 

union find

사이클이 발생하는지 안 하는지 어떻게 알까? 합집합(union find) 알고리즘을 사용한다.

같은 그래프에 속하는 두 노드를 연결할 때 사이클이 발생하므로, union find 알고리즘의 find 연산을 통해 '두 원소가 같은 그래프에 속하는지' 판단할 수 있다.

자세한 내용은 여기에서 다루고 있다.

(개인적으로 크루스칼 알고리즘은 이해가 쉬웠는데 union find 가 까다로웠다)

 

 

시간복잡도

union find 알고리즘이 상수 시간복잡도 $O(1)$을 가지기 때문에, 전체 시간복잡도를 좌우하는 것은 간선 가중치 정보를 정렬하는 로직이다.

가장 일반적인 퀵 정렬을 따른다면 시간복잡도는 $O(E \log E)$를 가진다. ($E$는 간선의 개수)

 

 

파이썬 코드

백준 1197번 최소 스패닝 트리 예제를 통해 알아보자

https://woo-niverse.tistory.com/228

[백준/약점체크] 1197번: 최소 스패닝 트리