최소 신장 트리(MST) : 크루스칼(Kruskal) & 프림(Prim)

최소 신장 트리

최소 신장 트리를 구하라

라는 문장을 코딩테스트를 하면 많이 볼 수 있다.

이 문장의 뜻은 간선에 비용이 있는 그래프에서 간선을 선택하여 모든 정점을 연결하였을 때, 비용의 합이 최소가 되도록 함을 의미한다.

- 각 시점에서 최선의 선택을 하는 알고리즘인 그리디(Greedy) 알고리즘 부류입니다.

 

신장트리

- 모든 정점을 연결하는 간선의 집합.

 

크루스칼(Kruskal) 알고리즘

- 크루스칼을 이용하여 최소 신장 트리를 구하는 방법은 다음과 같습니다.

 

1) 간선을 오름차순으로 정렬한 다음

2) 간선 하나씩 선택하며 폐로(사이클)이 생기는지 확인한 뒤,

3) 생기지 않으면 간선 리스트에 추가를, 생기면 간선 리스트에 접근 금지를 한다.

반복하다보면 모든 정점이 연결될 것입니다.

 

ex) 최소 신장 트리를 만들어라.

1) 가장 작은 간선인 1을 선택합니다. (폐로(사이클)이 없으니 간선 리스트에 추가합니다.)

2) 가장 작은 간선인 2를 선택합니다. (* 같은 값의 간선 중 아무거나 선택해도 됩니다.)

3) 가장 작은 간선인 2를 선택합니다. 

4) 가장 작은 간선인 2를 선택합니다. (폐로(사이클)가 발생하므로 E-F는 선택될 수 없음.)

따라서 그다음 값인 3을 선택합니다.

5) 4도 마찬가지로 폐로(사이클)가 발생하므로, 패스하고 5를 선택합니다.

6) 6도 폐로(사이클)가 발생하므로 패스하고 7을 선택합니다.

7) 8도 폐로(사이클)가 발생하므로 패스하면 끝이 납니다.

 

시간복잡도

정점의 수: n, 간선의 수 : m 일때, m회 이내로 반복을 마칩니다.

O(m log m) : 간선을 비용의 순서대로 정렬해야 하기 때문에 시간복잡도는 m log m이 된다.

폐로 탐색

- 매번 탐색하면 시간이 오래 걸립니다. 따라서 서로소 집합 데이터 구조와 합칩합 찾기(Union-Find)를 이용하면 O(m log n)이 되는데,

n<=m이기 때문에 O(m log m)이 됩니다.

 

 

프림(Prim) 알고리즘

- 크루스칼과 마찬가지로 최소 신장 트리를 구현하는데 사용되는 알고리즘입니다.

- 프림 알고리즘의 동작 로직은 다음과 같습니다.

1) 아무 정점 하나를 선택합니다.

2) 정점에 연결된 간선들 중 가장 작은 값을 선택한다.

3) 해당 간선으로 인해 폐로(사이클)가 생기는지 확인 후 이상 없다면 반대편 정점을 연결합니다.

4) 계속해서 반복하다보면 모든 정점이 연결됩니다.

 

ex) 아래 그래프에서 최소 신장 트리를 만들어라.

1) 정점 하나를 선택합니다. (랜덤으로 D로 결정)

연결된 간선들 중 가장 작은 값을 선택합니다.

2) 폐로(사이클)가 없으므로 F도 연결됩니다.

F에서의 간선들도 정렬합니다.

3) C-F 또는 E-F의 값이 2로 가장 작으므로 C-F를 선택했습니다.

4) C에서의 간선들도 목록에 포함합니다.

5) B-C가 1로 가장 작으므로 B도 연결합니다.

6) B에서의 간선들도 추가합니다.

7) B-E, E-F가 2로 가장 작습니다. (B-E로 선택했습니다.)

8) E에서의 간선들을 추가해줍니다. (E-G 추가)

9) E-F가 2로 가장 작지만, 폐로(사이클)가 생기므로 제외합니다. (같은 이유로 B-D, D-E,도 제외합니다.)

10) A-B가 5로 가장 작아서 정점 A가 연결됩니다.

11) A-C, C-D가 6이지만, 폐로(사이클)가 생기므로 제외합니다.

12) F-G가 7로 가장 작습니다. G 정점을 연결합니다.

13) E-G가 가장 작지만, 폐로(사이클)가 생기므로 제외합니다. 결과적으로 이렇게 최소 신장 트리 찾기가 끝이 납니다.

 

시간복잡도

- 단순하게 구현하면 O(nm)시간, 최적의 구조를 사용하면 O(m log n)의 시간이 걸립니다.