최소 신장 트리(MST)란 무엇인가?
최소 신장 트리(Minimum Spanning Tree, MST) 또는 최소 가중치 신장 트리는 가중치가 부여된 연결 그래프에서 모든 정점(vertex)을 연결하면서 사이클(cycle)을 만들지 않고, 간선 가중치의 총합이 최소가 되도록 선택한 간선들의 부분 집합을 의미합니다.
쉽게 말해, 그래프의 모든 노드를 잇되 불필요한 간선은 제거하고, 전체 연결 비용이 가장 작아지도록 만든 트리라고 할 수 있습니다. 여기서 '신장(spanning)'이라는 말은 그래프의 모든 정점을 포함한다는 뜻이며, '트리'라는 점에서 간선의 개수는 반드시 정점의 수 - 1개가 됩니다.
MST의 주요 특징
- 모든 정점 포함: 원본 그래프에 있는 모든 정점이 반드시 트리에 포함됩니다.
- 사이클 없음: 트리의 성질에 따라 어떤 두 정점 사이에도 경로가 유일하며 순환 구조가 존재하지 않습니다.
- 최소 가중치 합: 가능한 신장 트리 중에서 간선 가중치의 총합이 가장 작습니다.
- 간선 개수: 정점이 V개일 때, MST의 간선은 항상 V - 1개입니다.
대표적인 MST 알고리즘
MST를 찾는 데 널리 사용되는 알고리즘은 크게 두 가지가 있습니다.
1. 크루스칼(Kruskal) 알고리즘
모든 간선을 가중치 오름차순으로 정렬한 뒤, 사이클을 만들지 않는 간선부터 하나씩 선택하는 방식입니다. 사이클 여부는 유니온-파인드(Union-Find, 서로소 집합) 자료구조를 활용해 효율적으로 판별할 수 있으며, 시간 복잡도는 O(E log E)입니다.
2. 프림(Prim) 알고리즘
임의의 시작 정점에서 출발하여, 현재 트리에 연결된 간선 중 가장 가중치가 낮은 간선을 반복적으로 추가하며 트리를 확장합니다. 우선순위 큐(최소 힙)를 사용하면 시간 복잡도를 O(E log V)까지 줄일 수 있습니다.
JavaScript 구현 예시 (크루스칼 알고리즘)
class UnionFind {
constructor(n) {
this.parent = Array.from({ length: n }, (_, i) => i);
}
find(x) {
if (this.parent[x] !== x) {
this.parent[x] = this.find(this.parent[x]); // 경로 압축
}
return this.parent[x];
}
union(a, b) {
const rootA = this.find(a);
const rootB = this.find(b);
if (rootA === rootB) return false; // 이미 같은 집합 → 사이클 발생
this.parent[rootB] = rootA;
return true;
}
}
function kruskalMST(numVertices, edges) {
const sortedEdges = [...edges].sort((a, b) => a.weight - b.weight);
const uf = new UnionFind(numVertices);
const mst = [];
let totalWeight = 0;
for (const { from, to, weight } of sortedEdges) {
if (uf.union(from, to)) {
mst.push({ from, to, weight });
totalWeight += weight;
}
if (mst.length === numVertices - 1) break; // 완성
}
return { mst, totalWeight };
}MST의 실무 활용 분야
- 네트워크 설계: 통신망, 전력망, 상수도 관로 등 모든 지점을 최소 비용으로 연결할 때 활용됩니다.
- 도로 및 철도 건설: 여러 도시를 잇는 도로망을 최소 공사비로 계획할 때 사용됩니다.
- 클러스터링: 데이터 분석에서 MST를 응용해 밀도 기반 군집화를 수행할 수 있습니다.
- 회로 설계: 배선 길이를 최소화하는 PCB 회로 설계에 적용됩니다.
마무리
최소 신장 트리는 그래프 이론에서 가장 실용적인 개념 중 하나로, 최적화 문제를 해결하는 강력한 도구입니다. JavaScript로 구현할 때는 크루스칼 알고리즘이 간선 정렬과 유니온-파인드만으로 직관적으로 작성할 수 있어 입문자에게 특히 적합합니다. 코딩 테스트나 알고리즘 학습에서 MST 문제를 자주 만나므로, 두 대표 알고리즘의 동작 원리와 차이점을 확실히 이해해 두는 것이 좋습니다.