정렬한 뒤 판단한다
전체 간선을 가중치가 작은 순서로 살핀다. 간선의 두 끝이 이미 선택된 간선들로 이어져 있다면 그 간선을 더할 때 순환이 생기므로 건너뛴다. 연결되지 않았다면 선택해 두 부분을 합친다.
작은 가중치만 고르면 되는가
가벼운 간선이라고 무조건 넣는 것은 아니다. 세 정점의 삼각형에서 두 간선을 고른 뒤 남은 세 번째 간선까지 넣으면 순환이 된다. 정렬 순서와 함께 연결 상태를 검사해야 한다.
연결 상태의 관리
서로소 집합 자료 구조를 이용하면 두 끝이 같은 성분인지 확인하고 다른 성분을 합칠 수 있다. 간선 정렬과 성분 판정은 서로 다른 역할을 맡는다.
프림과 비교
프림은 하나의 트리에서 바깥으로 확장한다. 크루스칼은 서로 떨어진 여러 트리를 유지하다가 합친다. 연결 그래프에서는 최소 신장 트리를, 분리된 그래프에서는 각 성분의 최소 신장 트리로 이루어진 숲을 얻을 수 있다.
관련 문서
최소 신장 트리 / 신장 트리 / 프림 알고리즘 / 가중 그래프 / 연결 성분 / 트리 (그래프 이론) / 정렬 알고리즘