크루스칼 알고리즘 (Kruskal's Algorithm)

한 줄 정의: 그래프의 간선들을 비용이 싼 순서대로 하나씩 골라, 사이클이 생기지 않게 이어 붙여서 가장 저렴하게 모든 정점을 연결하는 알고리즘입니다.

쉽게 풀면

여러 마을을 도로로 연결해야 하는데, 예산이 한정되어 있다고 해봅시다. 가장 좋은 전략은 "건설 비용이 가장 싼 도로부터" 하나씩 놓는 것입니다. 단, 이미 연결된 마을들끼리 다시 도로를 놓아 원(순환 경로)이 생기는 건 예산 낭비이므로 건너뜁니다. 이렇게 싼 도로부터 순서대로 골라 원이 생기지 않을 때만 놓다 보면, 모든 마을이 연결되는 순간 전체 비용이 가장 적은 도로망이 완성됩니다. 이것이 바로 크루스칼 알고리즘의 원리이며, 결과물은 최소 신장 트리라고 부릅니다.

왜 중요한가

크루스칼 알고리즘은 네트워크 설계, 클러스터링, 회로 배선 등 "가장 저렴하게 전체를 연결하는 구조"를 찾아야 하는 다양한 문제의 기초가 됩니다. 계산 복잡도 분석이나 자료구조(유니온-파인드) 설계와도 밀접하게 연결되어 있어, 알고리즘 및 그래프 이론을 다루는 논문에서 비교 기준이나 전처리 단계로 자주 등장합니다. 또한 최소 신장 트리라는 개념 자체가 이미지 분할, 근사 알고리즘 등 여러 응용 분야의 이론적 토대로 쓰이기 때문에 그 중요성이 큽니다.

논문에서는 이렇게 쓰입니다

"센서 네트워크의 배선 비용을 최소화하기 위해 크루스칼 알고리즘(Kruskal's algorithm)을 적용하여 최소 신장 트리를 구성하였다."

이 문장은 여러 센서를 연결하는 통신선의 총 길이(비용)를 가장 짧게 만드는 연결 구조를 크루스칼 알고리즘으로 찾아냈다는 뜻입니다.

"이미지 분할(image segmentation) 과정에서 픽셀 간 유사도를 간선 가중치로 정의하고, 크루스칼 알고리즘 기반의 최소 신장 트리를 이용해 영역을 군집화하였다."

영상 처리 분야에서는 픽셀들을 노드로, 픽셀 간 색상·밝기 차이를 간선 비용으로 보고 크루스칼 알고리즘으로 비슷한 영역끼리 묶어 이미지를 나누는 데 활용됩니다.

"군집 분석(clustering)에서 계층적 군집 구조를 얻기 위해 최소 신장 트리를 크루스칼 방식으로 구성한 뒤, 가장 비용이 큰 간선을 순차적으로 제거하는 방법을 제안하였다."

데이터 마이닝 분야에서는 데이터 포인트들을 하나의 트리로 연결한 뒤 비용이 큰 연결을 끊어나가는 방식으로 자연스러운 군집을 찾아내는 데 크루스칼 알고리즘이 쓰입니다.

조금 더 깊게 보면

크루스칼 알고리즘의 실행 속도는 간선을 정렬하는 비용과, 사이클 발생 여부를 빠르게 확인하는 유니온-파인드 자료구조의 효율성에 크게 좌우됩니다. 경로 압축(path compression)과 랭크에 의한 합치기(union by rank) 같은 최적화 기법을 함께 쓰면 사이클 검사 비용을 거의 상수 시간에 가깝게 줄일 수 있어, 전체 알고리즘의 성능은 대체로 간선 정렬 비용이 지배합니다. 한편 최소 신장 트리는 유일하지 않을 수 있는데, 간선 가중치에 동률(tie)이 있는 경우 서로 다른 정렬 순서에 따라 다른 트리가 나올 수 있다는 점도 이해해 두면 논문을 읽을 때 도움이 됩니다.

주의할 점

크루스칼 알고리즘은 간선을 기준으로 비용이 싼 순서대로 훑어나가는 방식이라, 정점을 기준으로 가장 가까운 지점부터 넓혀가는 다익스트라 알고리즘과는 목적과 방식이 다릅니다. 다익스트라는 "한 지점에서 다른 모든 지점까지의 최단 경로"를 찾지만, 크루스칼은 "전체를 잇는 가장 저렴한 연결망"을 찾는다는 점에서 구분해야 합니다.