[MST]
N개의 핀을 두개씩 연결하기 위해서는 N-1개의 선이 필요하다. 여기서 방향이 없는 그래프 G = (V, E)가 사용되며 V는 핀의 집합, E는 핀 쌍의 가능한 연결 집합이다. 그리고 각 edge(u,v)는 E에 포함된다. 가중치(w)s는 u와v를 연결하는 데 드는 비용을 나타낸다. MST의 목표는 모든 노드를 연결할 때(비순환) 총 비용이 가장 적은 순환을 찾는 것이다.
그래프 T는 비순환적이고 모든 정점을 연결하므로, 이는 하나의 트리를 형성하게 된다. 이는 그래프 G를 "포괄(spans)"하기 때문에 스패닝 트리(spanning tree)라고 부른다. T를 결정하는 문제를 우리는 최소신장 트리 문제로 부르기로 하였다.
다음 그림은 연결된 그래프와 최소신장 트리 문제의 예시를 보여준다.
이 챕터에서 우리는 두개의 최소 신장 트리 문제를 푸는 방법을 연구한다. Kruskal 알고리즘과 Prim 알고리즘 모두 O(E lg V)시간 복잡도를 가진다. Prim 알고리즘은 우선순위 큐로 바이너리 힙을 사용해서 문제를 풀었다. 피보나치 힙 대신 사용함으로써 Prim 알고리즘은 O(E + V lg V)시간 복잡도를 가진다. 이 방식은 ∣E∣가 ∣V∣보다 점근적으로 더 빠르게 증가할 때, O(∣E∣lg∣V∣)보다 더 나은 성능을 제공한다.
두 개의 알고리즘은 greedy 알고리즘으로 묘사된다. greedy 알고리즘의 각 스텝은 반드시 여러 가능한 가능성 중 하나를 골라야 한다. greedy는 매 순간마다 최선을 선택하는 전략이다. 이러한 전략은 일반적으로 항상 최선의 선택을 고른다는 것을 보장받지 못한다. 하지만 최소 신장 트리 문제에서 우리는 증명할 수 있다. 특정한 greedy 전략이 최소한의 비용이 드는 신장 트리를 산출한다는 것이다.
최소 신장 트리 문제의 입력은 가중치 함수 를 가진 연결된 무방향 그래프 G(V,E)이다. 목표는 그래프 G의 최소 신장 트리를 찾는 것이다.
일반적인 MST는 다음과 같다.
각 스텝은 A에 추가해도 불변조건을 위배하지 않는 edge(u, v)를 결정한다. 여기서 A는 최소 신장 트리의 부분 트리가 된다. 우리는 edge가 A에 추가될 때 불변성을 유지하면서 추가될 수 있을 때 이러한 edge를 safe edge라고 부르기로 한다.
이 일반적인 알고리즘은 다음과 같이 반복 불변식을 사용한다:
- 초기화: 1번 줄 이후, 집합 A는 반복 불변식을 만족한다.
- 유지: 2~4번 줄의 반복문은 안전한 간선만을 추가함으로써 불변식을 유지한다.
- 종료: A에 추가된 모든 간선은 최소 신장 트리에 속하며, 반복문은 모든 간선을 검토한 시점에서 종료해야 합니다. 따라서 5번 줄에서 반환된 집합 A는 최소 신장 트리여야 한다.
어려운 부분은 3번 줄에서 안전한 간선을 찾는 것이다. 하지만 이는 반드시 존재한다. 왜냐하면 3번 줄이 실행될 때, 불변 조건에 따라 A를 포함하는 스패닝 트리 T가 존재하기 때문이다.
while 루프 내부에서는 A가 의 적절한 부분 집합이어야 하며, 따라서 에 속하지만 A에는 포함되지 않은 간선 가 반드시 존재한다. 이 간선 는 에 대해 안전한 간선이어야 한다.