크루스칼의 최소 신장 트리

최소 신장 트리는 사이클 없이 전체 간선 가중치의 합을 최소화하면서 모든 정점을 연결합니다. 가장 적은 비용으로 마을에 전선을 연결한다고 생각해 보십시오. 🌲

크루스칼 알고리즘은 철저한 탐욕적 접근법을 사용합니다. 사이클을 만들지 않는 가장 저렴한 간선을 계속 추가하여 전체 그래프가 연결될 때까지 진행합니다.

먼저 모든 간선을 가중치 기준으로 가장 작은 것부터 sort합니다. 저렴한 간선을 우선하는 탐욕적 선택이 최종 합을 최소로 만듭니다.

간선을 추가했을 때 양 끝점이 이미 연결되어 있는 경우에만 사이클이 생깁니다. DSU는 이 연결성 검사를 거의 상수 시간에 수행합니다. 🤝

간선을 가장 저렴한 것부터 가장 비싼 것까지 차례로 살펴보십시오. 각 간선에 대해 양 끝점이 DSU에서 이미 같은 루트를 공유하는지 확인합니다.

루트가 다르면 간선이 서로 다른 두 부분을 연결하므로 해당 간선을 선택하고 둘을 합칩니다. 루트가 같으면 사이클을 피하기 위해 건너뜁니다.

n개의 정점을 가진 신장 트리는 정확히 n - 1개의 간선을 가집니다. 그만큼의 간선을 선택했다면 일찍 멈출 수 있습니다.

모든 간선을 살펴본 뒤 선택한 간선이 n - 1개보다 적다면 그래프는 연결되지 않은 상태이며 신장 트리가 존재하지 않습니다.

정렬이 대부분의 시간을 차지하므로 크루스칼 알고리즘은 O(E log E)에 실행됩니다. DSU 연산은 매우 저렴해서 전체 시간에 거의 영향을 주지 않습니다.

절단 성질은 어떤 분할을 가로지르는 가장 가벼운 간선은 추가해도 안전하다고 보장합니다. 이것이 가장 저렴한 간선부터 선택해도 잘못되지 않는 이유입니다.

크루스칼 알고리즘은 간선 목록으로 주어지는 희소 그래프에서 특히 빛납니다. 대부분의 대회 문제는 이 형식으로 그래프를 직접 제공합니다. ⚡

크루스칼 알고리즘이 간선을 거부하게 만드는 조건을 판단해 보십시오.

크루스칼의 MST를 만들었습니다. 간선을 정렬하고, DSU를 이용해 두 컴포넌트를 연결하는 가장 저렴한 간선을 추가한 뒤 n - 1개의 간선에서 멈춥니다. 🎉