최소신장트리, 크루스칼 알고리즘

나동빈님의 '이것이 코딩테스트다 with 파이썬'저서와 유튜브 강의를 참고하며 작성하였습니다. 

코드 출처: https://github.com/ndb796/python-for-coding-test

---

▶ 신장트리란?

그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. 모든 노드는 연결하기위해 모든 간선을 사용하지 않아도 된다는 점에서 모든 노드들이 연결되어있지만 최소한의 비용으로 구성되는 신장 트리를 찾아야할 때 효율적으로 사용될 수 있다. 

> 시간복잡도: 해당 알고리즘에서 가장 많은 시간을 요하는 곳이 간선의 정렬을 수행하는 부분으로 간선 개수가 E개 일때 O(ElogE)의 시간복잡도를 가진다. 

 

 

 

▶ 동작과정

step 1. 간선 비용을 오름차순으로 정렬하여 최소 비용의 간선부터 점검하도록 한다. 

step 2. 간선을 확인하며 간선이 같은 그룹에 속해있지 않으면 union연산을 수행한다. 즉 현재 간선이 사이클을 발생시키않는 경우에만 최소신장트리에 포함시키고 사이클을 발생시키면 제외한다. 

step 3. 모든 간선에 대해 step 1,2를 반복한 후 최소 신장 트리에 포함돼있는 간선의 비용만 모두 더하여 최종비용을 구한다. 

 

 

 

▷ 예시

다음과 같은 그래프가 있다고 해보자. 해당 그래프에서 모든 노드를 연결하는 최소비용을 구하고자 한다. 

step 1. 비용을 기준으로 오름차순으로 정렬했다. 앞쪽의 간선부터 차례대로 점검해보자. 

step 2 + step 3. 사이클을 발생시키지 않는 간선의 비용을 result에 더하자.

 

1) (2,3)은 사이클을 발생시키지 않기 때문에(루트노드가 다르기 때문에) union연산하여 루트노드를 통일시킨 후 result에 2를 더한다. -> result= 2

 

2) (1,4)는 사이클을 발생시키지 않기 때문에 union연산한 후 result에 3을 더한다. -> result =5

 

3) (1,2)역시 사이클을 발생시키지 않기 때문에 union연산 후 result에 5를 더한다. -> result =10

 

4) (3,5)역시 사이클을 발생시키지 않기 때문에 union연산 후 result에 6을 더한다 -> result =16

5) (1,3)과 (3,4)는 같은 루트노드 1에 속하기 때문에 사이클을 발생시킨다. 따라서 union연산을 하지 않고 result 연산에서도 제외된다. 

6) 따라서 모든 노드를 연결하는 최소비용은 16임을 알 수 있다. 

 

 

 

▷ 구현

- 루트노드를 찾는 함수와 union연산함수를 생성한다. 

 

- 위 예제에 해당하는 데이터들을 입력한다

- 최소 비용을 산출한다. 

최소 비용이 16으로 예시 작동과정과 동일하게 작동된다.