크러스컬 알고리즘: 두 판 사이의 차이

# 알고리즘의 마지막 단계로 n-1개의 변이 남은 그래프인 생성나무가 최소비용 생성나무를 포함함을 보임으로써 결과로 나온 생성나무가 최소비용임을 보인다. n개의 변이 남았을 때, 그래프를 F라 하고 F가 포함하는 최소비용 생성나무를 T라고 하자. 그리고 F에서 변 e를 제거하여 알고리즘이 끝난다고 하자. T가 나무이고 회로를 가지지 않으므로 n-1개의 변을 가진다. F에서 변 f를 제거하면 T가 된다고 하자. 알고리즘에서 최대 가중치를 가진 변을 제거하므로 e의 가중치는 f 이상이다. 그러므로 F-e는 T의 비용 이하의 생성나무이다. 그런데 T는 최소비용 생성나무이므로 F-e는 T와 비용이 같다. 즉 F-e는 최소비용 생성나무이고 자신을 포함한다.

 

1 '''function''' Kruskal(''G'')

2 '''for each''' vertex ''v'' in ''G'' do