KruskalMST

크러스컬 최소 신장 트리 (Kruskal MST) 가중치가 가장 작은 선분이 사이클을 만들지 않을 때만 그리디하게 선분 추가 Pseudo code KruskalMST(G) Input: 가중치 그래프 G = (V, E), |V| = n, |E| = m Output: 최소 신장 트리 T 1. 가중치의 오름차순으로 선분들을 정렬한다. 정렬된 선분 리스트를 L이라고 하자. 2. T = ∅ // 트리 T를 초기화시킨다. 3. while ( T의 선분 수 < n-1 ) { 4. L에서 가장 작은 가중치를 가진 선분 e를 가져오고, e를 L에서 제거한다. 5. if (선분 e가 T에 추가되어 사이클을 만들지 않으면) 6. e를 T에 추가시킨다. 7. else // e가 T에 추가되어 사이클이 만들어지는 경우 8. e..