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

MST란?

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

조건

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

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

대표 알고리즘

Kruskal 알고리즘

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

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

Prim 알고리즘

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

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

Union-Find 자료구조

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

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 구현

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 구현

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 구현

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 최적화로 매우 빠르게 동작합니다.