크루스칼 알고리즘 (MST, 최소 신장 트리, kruskal)

---

 

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

그래프 내의 모든 정점을 포함하면서 사용된 간선들의 가중치 합이 최소가 되는 트리 

 

MST 특징

1) 간선(Edge)의 가중치 합이 최소

2) N개의 정점을 가지는 그래프에서 반드시 (N - 1) 개의 간선만을 사용해야 함 (= 트리의 성질)

3) Cycle을 포함하면 안된다

 

 

크루스칼(Kruskal) 알고리즘 

- 최소 신장 트리(MST)를 구하는 알고리즘 중 하나

- 매 순간 최소 가중치를 가지는 간선을 선택하여 연결하므로, 탐욕 알고리즘으로도 분류됨

- 이때 Union-Find 알고리즘과 함께 사용하여 Cycle 형성되지 않을 경우 노드를 연결한다

- 시간복잡도 : O(ElogE) 

- 실제 로직보다 간선 정보 정렬시 비용이 가장 큰 걸로 알려져 있다

 

절차

1) 그래프 간선에 대한 정보를 정의하고 가중치가 작은 순으로 오름차순 정렬한다.

2) 정렬된 간선 리스트를 반복문을 통해 순회하면서, 사이클 형성하지 않은 간선을 선택 

- 부모 노드가 같지 않는 경우 집합(연결) 처리 (이때 부모 노드 크기 비교하여 작은 부모 노드로 갱신)

- 부모 노드가 같은 경우 이미 연결된 노드로 사이클 형성 가능하여 선택하지 않음

3) 해당 간선을 MST 집합에 추가하고 간선의 가중치를 합산

 

 

참고. 동빈나 강사님 유튜브 채널 

https://www.youtube.com/watch?v=LQ3JHknGy8c&t=528s 

 

 

 

크루스칼 알고리즘 예시

위키 백과 참고

 

1) 초기화 

- 간선 정보를 초기화하고 가중치 오름차순 정렬 

- 노드의 개수만큼 배열 크기를 잡고, 자기 자신을 부모노드로 가르키도록 초기화

 

이제 반복문을 동해 순차적으로 간선 정보 조회하면서 연결하도록 합니다

 

 

2) A - D 연결

- A와 D 는 각각 자기자신을 부모노드로 가르키고 있음 (Union-Find)

- A가 알파벳 순으로 작으므로 D의 부모노드를 D -> A로 갱신 (집합처리, Union)

- 가중치를 합산한다 (총 비용 : 5)

 

 

 

3) C - E 연결

- C와 E 는 각각 자기자신을 부모노드로 가르키고 있음 (Union-Find)

- C가 알파벳 순으로 작으므로 E의 부모노드를 C -> E로 갱신 (집합 처리, Union)

- 가중치를 합산한다 (총 비용 : 10)

 

 

 

4) D - F 연결

- D와 F는 서로 다른 부모 노드를 가르키고 있음 (Union-Find)

- D노드의 부모인 A가 알파벳 순으로 작으므로 F의 부모노드를 F -> A로 갱신 (집합 처리, Union)

- 가중치를 합산한다 (총 비용 : 10 + 6 = 16)

 

 

5) A - B 연결

- A와 B는 서로 다른 부모 노드를 가르키고 있음 (Union-Find)

- A노드의 부모인 A가 알파벳 순으로 작으므로 B의 부모노드를 B -> A로 갱신 (집합 처리, Union)

- 가중치를 합산한다 (총 비용 : 16 + 7 = 23)

 

6) B - E 연결

- B와 E는 서로 다른 부모 노드를 가르키고 있음 (Union-Find)

- B노드의 부모인 A가 알파벳 순으로 작으므로, E의 부모노드 재귀 탐색시 C 노드의 부모노드 C -> A로 갱신 (집합 처리, Union)

- 가중치를 합산한다 (총 비용 : 23 + 7 = 30)

 

7) B - C (사이클 형성) 

- B와 C는 같은 부모 노드 A를 가짐 

- 이는 곧 같은 집합에 속한다는 뜻으로, 이번에 연결하게 될 경우 사이클 형성하게 되므로 continue

 

8) E - F (사이클 형성) 

- Union-Find 알고리즘 통해 E의 부모노드가 A로 갱신됨

- E와 F는 같은 부모 노드 A를 가짐 

- 이는 곧 같은 집합에 속한다는 뜻으로, 이번에 연결하게 될 경우 사이클 형성하게 되므로 continue

 

9) B - D (사이클 형성) 

마찬가지로 동일한 부모노드 A를 가르키므로 연결시 사이클 형성하니 continue

 

10) E - G 연결

- E와 G는 서로 다른 부모 노드를 가르키고 있음 (Union-Find)

- E노드의 부모인 A가 알파벳 순으로 작으므로, G의 부모 노드를 G -> A로 갱신 (집합 처리, Union)

- 가중치를 합산한다 (총 비용 : 30 + 9 = 39)

 

- 이후 나머지는 사이클 형성하므로 continue 처리 (종료)

- 총 비용 39에 MST를 만들 수 있었습니다.

 

 

백준 추천 문제

1. 우주신과의 교감(골드3)

2. 전력난(골드4)

3. 악덕 영주 혜유(골드2)

4. 행성터널(플래티넘5)

5. MST 게임(골드3)

 

풀이 참고 

https://dev-ljw1126.tistory.com/362

[BOJ1774] 우주신과의 교감 (그리디, 크루스칼, MST, 최소신장트리)

https://dev-ljw1126.tistory.com/364

[BOJ6497] 전력난 (크루스칼, 프림, 최소 신장트리, MST)

https://dev-ljw1126.tistory.com/369

[BOJ20010] 악덕 영주 혜유 (크루스칼, 프림, MST, 최소신장트리, 트리의 지름)

https://dev-ljw1126.tistory.com/385

[BOJ2887] 행성 터널(최소신장트리,MST, 크루스칼 알고리즘)