MST/DSU

최소 신장 트리는 사이클 없이 모든 정점을 가장 싸게 잇는다

Kruskal, Prim, DSU, find(u)==find(v), V-1 조건은 MST 코드의 판단 축입니다.

DSU

find는 대표를 찾고 union은 두 집합을 합칩니다

경로 압축과 rank/size 기준을 쓰면 연산이 매우 빨라집니다.

Kruskal

크루스칼 선택 조건

find(u)==find(v)이면 이미 같은 컴포넌트라 건너뜁니다.

Prim

MST 우선순위 큐 선택

정점 중심으로 확장하므로 조밀한 그래프에서 간선 정렬 방식과 선택 기준을 비교합니다.

V-1

MST 간선 수 조건

선택 간선 수가 부족하면 그래프가 연결되지 않은 것입니다.

사이클 MST는 모든 정점을 잇되 닫힌 순환을 만들지 않습니다.
정렬 비용 Kruskal은 간선 정렬이 전체 비용의 큰 부분입니다.
시작 정점 Prim은 시작점이 달라도 연결 그래프에서는 같은 총 비용을 얻습니다.