최소 스패닝 트리(MST) 알고리즘

그래프에서 모든 노드를 최소 비용으로 연결하는 문제는 네트워크 설계, 클러스터링, 회로 설계 등 다양한 분야에서 핵심적으로 등장한다. MST 알고리즘은 이 문제를 효율적으로 해결하며, 통신망 구축 비용 최소화나 데이터 포인트 간 유사도 기반 군집화에도 활용된다.

MST란?

**최소 스패닝 트리(Minimum Spanning Tree)**는 가중치가 있는 연결 그래프에서 모든 정점을 연결하면서 가중치의 합이 최소가 되는 트리이다.

조건

모든 정점을 연결 (Spanning)
사이클이 없음 (Tree)
가중치 총합이 최소 (Minimum)

따라서 MST는 $V-1$ 개의 간선으로 모든 정점을 연결하는 가중치 최소 트리이다.

대표 알고리즘

Kruskal 알고리즘

모든 간선을 가중치 기준 오름차순 정렬
가중치가 작은 간선부터, 사이클이 생기지 않으면 MST에 추가
MST의 간선이 $V-1$ 개가 되면 종료

시간복잡도: $O(E \log E)$ 적합한 경우: 희소 그래프 (Sparse Graph)

Prim 알고리즘

임의의 시작 정점에서 시작
연결된 간선 중 가장 가중치가 작은 간선 선택
선택된 정점 집합과 미선택 집합을 잇는 최소 간선 반복 추가

시간복잡도: $O(E + V \log V)$ (우선순위 큐 사용) 적합한 경우: 조밀 그래프 (Dense Graph)

Union-Find 자료구조

Kruskal 알고리즘의 핵심으로, 사이클 판별에 사용된다.

Union-Find는 원소들이 같은 집합에 속하는지 판별하고, 두 집합을 합치는 자료구조이다. find 연산은 루트 노드를 찾으면서 경로를 압축하고, union 연산은 랭크 기반으로 작은 트리를 큰 트리에 붙여 균형을 유지한다.

python

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])  # 경로 압축
    return parent[x]
 
def union(a, b):
    root_a, root_b = find(a), find(b)
    if root_a != root_b:
        if rank[root_a] < rank[root_b]:
            parent[root_a] = root_b
        elif rank[root_a] > rank[root_b]:
            parent[root_b] = root_a
        else:
            parent[root_b] = root_a
            rank[root_a] += 1

예시 그래프

간선	가중치
(0,1)	10
(0,2)	6
(0,3)	5
(1,3)	15
(2,3)	4

MST 결과: (2,3), (0,3), (0,2) → 총 가중치 15

Python 구현

Python 구현은 간선을 가중치 기준으로 정렬한 뒤 Union-Find로 사이클 여부를 판별한다.

python

def kruskal_mst(vertices, edges):
    """
    vertices: 정점 개수
    edges: (weight, src, dest) 튜플 리스트
    """
    edges.sort(key=lambda x: x[0])
 
    parent = list(range(vertices))
    rank = [0] * vertices
 
    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]
 
    def union(a, b):
        root_a, root_b = find(a), find(b)
        if root_a != root_b:
            if rank[root_a] < rank[root_b]:
                parent[root_a] = root_b
            elif rank[root_a] > rank[root_b]:
                parent[root_b] = root_a
            else:
                parent[root_b] = root_a
                rank[root_a] += 1
            return True
        return False
 
    mst_weight = 0
    mst_edges = []
 
    for w, s, d in edges:
        if union(s, d):
            mst_weight += w
            mst_edges.append((s, d, w))
 
    return mst_weight, mst_edges
 
 
# 실행
edges = [(10, 0, 1), (6, 0, 2), (5, 0, 3), (15, 1, 3), (4, 2, 3)]
weight, mst = kruskal_mst(4, edges)
print(f"MST 총 가중치: {weight}")  # 15

Java 구현

Java 구현은 Edge 클래스를 Comparable로 정의하여 정렬하고, UnionFind 클래스로 집합 연산을 수행한다.

java

class Edge implements Comparable<Edge> {
    int src, dest, weight;
 
    Edge(int s, int d, int w) {
        this.src = s; this.dest = d; this.weight = w;
    }
 
    public int compareTo(Edge other) {
        return this.weight - other.weight;
    }
}
 
class UnionFind {
    int[] parent, rank;
 
    UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
    }
 
    int find(int x) {
        if (parent[x] != x)
            parent[x] = find(parent[x]);
        return parent[x];
    }
 
    void union(int a, int b) {
        int rootA = find(a), rootB = find(b);
        if (rootA != rootB) {
            if (rank[rootA] < rank[rootB]) parent[rootA] = rootB;
            else if (rank[rootA] > rank[rootB]) parent[rootB] = rootA;
            else { parent[rootB] = rootA; rank[rootA]++; }
        }
    }
}

Go 구현

Go 구현은 구조체와 포인터 리시버를 활용하여 Union-Find를 구현하고, union 메서드가 합치기 성공 여부를 bool로 반환한다.

type Edge struct {
    src, dest, weight int
}
 
type UnionFind struct {
    parent, rank []int
}
 
func NewUnionFind(n int) *UnionFind {
    uf := &UnionFind{
        parent: make([]int, n),
        rank:   make([]int, n),
    }
    for i := 0; i < n; i++ {
        uf.parent[i] = i
    }
    return uf
}
 
func (uf *UnionFind) find(x int) int {
    if uf.parent[x] != x {
        uf.parent[x] = uf.find(uf.parent[x])
    }
    return uf.parent[x]
}
 
func (uf *UnionFind) union(a, b int) bool {
    rootA, rootB := uf.find(a), uf.find(b)
    if rootA != rootB {
        if uf.rank[rootA] < uf.rank[rootB] {
            uf.parent[rootA] = rootB
        } else if uf.rank[rootA] > uf.rank[rootB] {
            uf.parent[rootB] = rootA
        } else {
            uf.parent[rootB] = rootA
            uf.rank[rootA]++
        }
        return true
    }
    return false
}

정리

알고리즘	시간복잡도	적합한 그래프
Kruskal	$O(E \log E)$	희소 그래프
Prim	$O(E + V \log V)$	조밀 그래프

Union-Find는 Kruskal 알고리즘의 핵심으로, 경로 압축과 union-by-rank 최적화로 매우 빠르게 동작한다.