최소 신장 트리 (Minimum Spanning Tree)
쉽게 풀면
여러 도시를 도로로 연결한다고 생각해봅시다. 모든 도시를 서로 오갈 수 있게 만들어야 하는데, 도로를 놓는 비용은 최대한 아끼고 싶습니다. 이때 "모든 도시가 끊기지 않고 연결되면서도, 도로 건설 비용의 총합이 가장 적은" 도로망을 찾는 문제가 바로 최소 신장 트리 문제입니다. 대표적인 해법으로는 가장 저렴한 간선부터 순서대로 골라 나가되 사이클이 생기지 않게 하는 크루스칼(Kruskal) 알고리즘과, 한 정점에서 시작해 매번 연결 가능한 가장 저렴한 간선을 붙여 나가는 프림(Prim) 알고리즘이 있습니다. 두 방법 모두 결과적으로 정점이 N개면 정확히 N-1개의 간선만 남는 트리 구조를 만들어냅니다.
왜 중요한가
최소 신장 트리는 여러 대상을 연결하되 비용을 최소화한다는 매우 일반적인 문제 구조를 갖고 있어, 네트워크 설계뿐 아니라 클러스터링, 이미지 분할, 근사 알고리즘 설계 등 다양한 분야의 논문에서 하위 도구로 활용됩니다. 계산 복잡도가 잘 알려진 다항 시간 알고리즘으로 정확히 풀 수 있다는 점 때문에, 더 어려운 최적화 문제(예: 외판원 문제)의 근사 해법을 설계할 때 출발점이나 하한(lower bound) 계산에 쓰이기도 합니다.
논문에서는 이렇게 쓰입니다
이 문장은 "여러 노드를 모두 연결하면서 전체 연결 비용이 최소가 되는 트리 구조를 크루스칼 알고리즘으로 계산했다"는 뜻입니다. 통신망 설계, 클러스터링, 회로 배선 최적화 등에서 자주 사용됩니다.
데이터마이닝·머신러닝 분야에서, 최소 신장 트리를 직접적인 연결 문제가 아니라 데이터를 군집으로 묶는 클러스터링 알고리즘의 기반 구조로 활용했다는 의미입니다.
조합최적화 논문에서, 정확한 최적해를 구하기 어려운 문제를 최소 신장 트리를 이용해 성능이 보장된 근사해로 대신 구하는 기법을 설명할 때 쓰이는 표현입니다.
조금 더 깊게 보면
크루스칼과 프림 외에도 보르프카(Borůvka) 알고리즘 등 최소 신장 트리를 구하는 방법이 여러 가지 알려져 있으며, 그래프의 밀도(간선 수 대비 정점 수)에 따라 어떤 알고리즘이 더 효율적인지가 달라집니다. 또한 모든 간선의 가중치가 서로 다르면 최소 신장 트리는 유일하게 결정되지만, 가중치가 같은 간선이 여러 개 있으면 서로 다른 여러 개의 최소 신장 트리가 존재할 수 있다는 점도 이론적으로 자주 언급됩니다.
주의할 점
최소 신장 트리는 그래프 내 두 지점 사이의 "최단 경로"를 보장하지 않습니다. 전체 연결 비용의 합을 최소화할 뿐이며, 특정 두 정점 사이의 최단 거리를 구하려면 다익스트라 알고리즘과 같은 별도의 최단 경로 알고리즘을 사용해야 합니다.