알고리즘 8장
MST/DSU: Kruskal MST
Kruskal은 간선을 가중치 순으로 보며, 서로 다른 컴포넌트를 잇는 간선만 채택해 MST를 만듭니다.
상태 변화
간선 선택
1-2
w=1 accept
2-3
w=2 accept
1-3
w=3 skip
3-4
w=4 accept
불변식
점검
정렬
간선을 가중치 오름차순으로 정렬합니다.
사이클 검사
두 끝점의 대표자가 같으면 이미 연결되어 skip합니다.
채택
대표자가 다르면 간선을 선택하고 union합니다.
종료
선택 간선이 V-1개가 되면 MST가 완성됩니다.