크러스컬 알고리즘
간선을 정렬하고, 가장 짧은 것을 고르고, 절대 고리를 만들지 않는다. 크러스컬 알고리즘은 아마 가장 단순한 그리디 알고리즘이지만, 그래프의 모든 노드를 잇는 가장 저렴한 방법을 언제나 찾아냅니다.
아이디어
최소 신장 트리는 가중 그래프의 모든 노드를 가능한 가장 작은 간선 길이 합으로 연결합니다. 크러스컬 알고리즘은 시작 노드에서 트리 하나를 키우지 않습니다. 그래프 전체를 한꺼번에 보고, 모든 노드가 각자 하나의 조각인 상태에서 시작해, 쓸 수 있는 가장 짧은 간선으로 조각들을 계속 이어 조각이 하나만 남을 때까지 진행합니다.
단계별 설명
간선을 짧은 것부터 긴 것 순서로 정렬하고 그 순서대로 시도합니다. 간선의 양 끝이 서로 다른 조각에 있으면 트리에 더합니다. 두 조각은 하나가 됩니다. 양 끝이 이미 같은 조각에 있으면 그 간선은 사이클을 만들므로 건너뜁니다. 노드가 n개이면 트리는 n − 1개의 간선으로 완성되고, 나머지 간선은 볼 필요도 없습니다.
예제
길이 1인 A–B, 2인 B–C, 3인 A–C, 4인 C–D, 5인 B–D 간선이 있습니다. 크러스컬은 A–B를 더하고, 이어서 B–C를 더해 C를 조각 A–B에 잇습니다. 다음은 A–C이지만 A와 C는 이미 한 조각에 있으므로 사이클 A–B–C를 만들게 되어 건너뜁니다. C–D로 D가 합류하면 네 노드 모두가 간선 세 개로 된 트리 하나가 되고, 총길이는 7입니다. 가장 긴 간선 B–D는 시도조차 되지 않습니다.
유니온-파인드
크러스컬 알고리즘이 묻는 어려운 질문은 하나뿐입니다. 이 두 노드가 이미 같은 조각에 있는가? 유니온-파인드 구조가 이에 답합니다. 각 조각은 대표를 가리키는 링크로 이루어진 작은 트리입니다. find는 링크를 따라 대표를 찾고, union은 한 대표를 다른 대표 아래에 연결합니다. 거쳐 간 모든 노드가 대표를 바로 가리키게 하는 경로 압축과 크기 기준 합치기 덕분에 링크가 아주 짧게 유지되어, 질문 하나에 거의 상수 시간이 걸립니다.
역사와 속도
조지프 크러스컬(Joseph Kruskal)은 1956년 Proceedings of the American Mathematical Society에 실린 짧은 논문에서 이 알고리즘을 발표했습니다. 가장 느린 부분은 간선 정렬이므로 간선 E개에 대해 작업량은 E log E에 비례해 늘어납니다. 간선이 이미 정렬되어 있거나 길이가 작은 정수이면 거의 선형입니다.
직접 해 보기
앱을 열고 단계를 누르세요. 아직 시도할 간선은 그래프 아래에 짧은 것부터 표시됩니다. 두 조각을 잇는 간선은 초록색이 되고, 사이클을 만드는 간선은 빨간 점선으로 그려집니다. 그래프 곳곳에서 작은 조각 여러 개가 자라 합쳐지는 모습을 지켜보고, 마지막 간선들은 아예 시도되지 않는 경우가 많다는 점도 눈여겨보세요.
자주 묻는 질문
크러스컬 알고리즘은 왜 간선을 정렬하나요?
더하는 간선마다 아직 두 조각을 잇는 간선 중 가장 짧은 것이 되도록 하기 위해서입니다. 이 그리디한 선택은 컷 속성 덕분에 항상 안전하고, 건너뛴 간선은 모두 그것이 만들 사이클에서 가장 긴 간선이므로 결코 필요하지 않습니다.
서로소 집합 구조란 무엇인가요?
유니온-파인드의 다른 이름입니다. 서로 겹치지 않는 집합들, 여기서는 자라는 포레스트의 조각들을 관리하며, 원소가 어느 집합에 속하는지 알려 주고 두 집합을 빠르게 합칩니다.
크러스컬 알고리즘은 연결되지 않은 그래프에서도 작동하나요?
네. 연결되지 않은 조각을 잇는 간선은 없으므로, 그래프의 연결된 조각마다 트리 하나씩, 즉 최소 신장 포레스트로 끝납니다.
크러스컬 알고리즘은 다른 데에도 쓰이나요?
마지막 조각들이 합쳐지기 전에 일찍 멈추면 노드가 클러스터로 묶이는데, 이것이 단일 연결 군집화입니다. 간선 길이가 무작위인 격자에서 실행하면 미로가 만들어집니다.
시도해 볼 준비가 되셨나요?
브라우저에서 PictorX를 엽니다. 설치가 필요 없고 시작하는 데 신용 카드가 필요하지 않습니다.
크러스컬 알고리즘 해 보기