MST
V-1개 간선
모든 정점을 연결하면서 총 비용을 최소화한다.
MST + DSU
가장 싼 간선이 아니라 사이클 없는 연결을 고른다
Kruskal은 간선을 가중치 순서로 보되, DSU로 같은 컴포넌트인지 확인하고 안전한 간선만 채택한다.
Sort간선을 비용 오름차순
Find두 정점의 대표 확인
Union다르면 채택하고 합침
Kruskal
작은 간선부터
비용이 낮은 후보를 먼저 보지만 안전성 검사를 거친다.
DSU
사이클 판정
find(u)==find(v)이면 이미 연결되어 제외한다.
Stop
간선 수 확인
채택 간선이 V-1개가 되면 전체 연결이 완성된다.