최소비용 신장 트리

이번 포스트에서는 그래프 중의 최소비용 신장 트리 알고리즘에 대해 다루겠다.

 

최소비용 신장 트리 알고리즘의 제약 조건 : 

1. 그래프 내에 존재하는 edge들만 사용
2. n - 1개의 edge만 사용
3. Cycle을 형성할 수 있는 edge는 사용 불가

최소비용 신장 트리 알고리즘 (모두 greedy method 사용) : 

1. Kruskal
2. Prim
3. Sollin

---

Kruskal 알고리즘이란?

• 한 번에 하나의 edge씩 추가하면서 최소비용 트리 T를 생성
• Edge들을 비용의 오름차순으로 정렬한 후, 가장 비용이 적은 edge부터 선택(greedy)
• 선택된 edge는 기존에 선택된 edge들과 사이클을 형성하지 않을 경우에만 T에 포함
• 그래프 G가 연결되었으며, n > 0개의 vertex가 존재할 경우, 정확히 n - 1개의 edge가 선택됨
• 시간 복잡도 O(e log e)

Kruskal 동작 과정

Kruskal

• 엣지들을 비용 순서대로 정렬한다. (복잡도 : O(e log e))
• 최소 비용 엣지인 10으로 시작하여 차례대로 10, 12, 14, 16을 선택한다.
• 16 다음에는 17이지만 17을 선택하는 경우 사이클이 형성되므로 패스한다.
• 다시 차례대로 22을 선택하고 24는 역시 사이클을 형성하므로 패스한다.
• 마지막에 25를 선택하여 Kruskal 알고리즘을 끝낸다.

union-find 연산을 이용한 경우

• <0, 5> -> union(0, 5): {0, 5}
• <2, 3> -> union(2, 3): {2, 3}
• <1, 6> -> union(1, 6): {1, 6}
• <1, 2> -> union(1, 2): {1, 2, 3, 6}
• <3, 6> -> union(3, 6) -> 3, 6은 같은 집합이므로 사이클 발생

---

Prim 알고리즘이란?

• 한번에 하나의 엣지를 선택하여 최소비용 신장 트리를 생성(하나의 트리가 확장되는 과정)
• 단 하나의 vertex만 갖는 트리 T에서 시작
• T에 포함된 vertex와 포함되지 않은 vertex를 연결하는 엣지들 중에서 비용이 최소인 엣지를 T에 추가
• 시간 복잡도 O(n^2)

Prim 동작 과정

Prim

• 0번 노드부터 시작해서 갈 수 있는 엣지를 탐색한다.
• 10과 28이 있으나 10이 더 효율성이 좋으니 10을 선택한다.
• 위 과정 반복한다.

---

Sollin 알고리즘이란?

• 단계별로 T에 포함시킬 여러 엣지들을 동시에 선택 (동시성, 병렬성)
• 각 단계에서 선택된 엣지들은 그래프의 spanning forest를 구성
• 초기에는 엣지가 없으므로, forest에 vertex 수 만큼의 트리가 존재
• 각 단계에서 forest에 있는 각 트리에 대해 하나의 엣지를 선택
• 두 개의 트리에서 동일한 엣지를 선택할 수 있으므로, 중복된 엣지를 제거하는 절차가 필요
• 하나의 트리만 남거나, 혹은 추가할 엣지가 없을 경우 종료
• 시간 복잡도 O(n log n)

Sollin 동작 과정

Sollin

• 각 트리가 동시에 가장 효율성이 좋은 엣지(최소비용) 선택한다.
• 하나의 트리만 남을 때까지 반복한다.