여기서 증명하지 않겠지만 직관적으로도 분명히 알 수 있는 사실입니다. 그렇다면 탐욕 알고리즘으로 최소 비용 신장 트리를 구할 수 있다는 의미입니다. MST를 구할 때 관심 있는 것은 최소 비용 신장 트리 T의 새로운 정점 집합 V(T)는 아닙니다. 정의를 보면 V(G)=V(T)이기 때문입니다. 유일한 관심사는 바로 E(T)입니다. 탐욕 알고리즘을 적용하면 가장 일반적인 MST 알고리즘을 구할 수 있습니다.

1. 에지 집합 E의 어떤 원소도 가로지르지 않는 컷 cut(S, V-S)를 찾습니다.

2. 횡단 에지 중 가중치가 가장 작은 에지 e를 찾아 E=E U {e} 연산을 합니다.

3. 1과 2를 트리가 될 때까지 실행합니다.

앞서 정의한 탐욕 알고리즘의 과정을 그림으로 하나씩 살펴보겠습니다.

그림 13-3을 보면 집합 E=ø 공집합이므로 아무 컷이나 잡으면 됩니다. 이 그림에서는 컷 cut(S, V-S)에 대해 S={0}, V-S={1, 2, 3, 4}입니다.

▲ 그림 13-3 탐욕 알고리즘 1