최소 신장 트리 — 모든 노드를 최소 비용으로 연결하기

도시들을 도로로 연결하려 합니다. 모든 도시가 연결되면서 도로 건설 비용을 최소로 하려면 어떤 도로를 놓아야 할까요?

최소 신장 트리(MST)란

신장 트리(Spanning Tree) 는 그래프의 모든 정점을 포함하면서 사이클이 없는 연결 부분 그래프입니다. 최소 신장 트리(MST) 는 간선 가중치의 합이 최소인 신장 트리입니다.

특성:

정점 V개, 간선 V-1 개
모든 정점이 연결됨
사이클 없음
간선 가중치 합이 최소

왜 필요한가

네트워크 케이블링: 최소 비용으로 모든 건물 연결
도로 설계: 최소 건설 비용으로 모든 도시 연결
클러스터링: MST에서 가장 비싼 간선을 제거하면 클러스터가 됨
근사 알고리즘: TSP의 2-근사해를 MST로 구할 수 있음

크루스칼(Kruskal) 알고리즘

간선 중심 접근법입니다. 가장 가벼운 간선부터 선택하되, 사이클이 생기면 건너뜁니다.

동작 과정

모든 간선을 가중치 순으로 정렬
가장 가벼운 간선부터 순서대로 확인
두 정점이 같은 집합이면 (사이클) 건너뜀
다른 집합이면 간선을 MST에 추가하고 두 집합을 합침
V-1개의 간선을 선택하면 종료

구현

JAVA

public static int kruskal(int n, int[][] edges) {
    // 간선을 가중치 순으로 정렬
    Arrays.sort(edges, Comparator.comparingInt(e -> e[2]));

    UnionFind uf = new UnionFind(n);
    int totalWeight = 0;
    int edgeCount = 0;
    List<int[]> mstEdges = new ArrayList<>();

    for (int[] edge : edges) {
        int u = edge[0], v = edge[1], w = edge[2];

        if (uf.union(u, v)) { // 다른 집합이면 합침
            totalWeight += w;
            mstEdges.add(edge);
            edgeCount++;
            if (edgeCount == n - 1) break;
        }
    }

    return totalWeight;
}

시간 복잡도

간선 정렬: O(E log E)
Union-Find: O(E × α(V)) ≈ O(E)
전체: O(E log E)

프림(Prim) 알고리즘

** 정점 중심** 접근법입니다. 하나의 정점에서 시작하여 MST를 확장해 나갑니다.

동작 과정

임의의 시작 정점을 MST에 포함
MST에 연결된 간선 중 가장 가벼운 간선 선택
그 간선의 반대쪽 정점을 MST에 추가
V-1개의 간선을 선택하면 종료

우선순위 큐 구현

JAVA

public static int prim(List<List<int[]>> graph, int n) {
    boolean[] inMST = new boolean[n];
    // (가중치, 정점)
    PriorityQueue<int[]> pq = new PriorityQueue<>(
        Comparator.comparingInt(a -> a[0])
    );

    pq.offer(new int[]{0, 0}); // 시작 정점
    int totalWeight = 0;
    int count = 0;

    while (!pq.isEmpty() && count < n) {
        int[] curr = pq.poll();
        int w = curr[0], u = curr[1];

        if (inMST[u]) continue;
        inMST[u] = true;
        totalWeight += w;
        count++;

        for (int[] edge : graph.get(u)) {
            int v = edge[0], weight = edge[1];
            if (!inMST[v]) {
                pq.offer(new int[]{weight, v});
            }
        }
    }

    return totalWeight;
}

시간 복잡도

우선순위 큐(이진 힙): O((V + E) log V)
인접 행렬 + 배열: O(V²) — 밀집 그래프에서 유리

크루스칼 vs 프림

구분	크루스칼	프림
접근	간선 중심	정점 중심
자료구조	Union-Find	우선순위 큐
시간 복잡도	O(E log E)	O((V+E) log V)
적합한 그래프	희소 그래프 (E ≈ V)	밀집 그래프 (E ≈ V²)
구현	간선 리스트만 필요	인접 리스트 필요

MST의 성질

Cut Property

그래프를 두 집합 S와 V-S로 나누는 컷에서, 그 컷을 가로지르는 ** 가장 가벼운 간선 **은 반드시 MST에 포함됩니다.

이 성질이 크루스칼과 프림의 정당성을 보장합니다.

Cycle Property

그래프의 임의의 사이클에서 ** 가장 무거운 간선 **은 MST에 포함되지 않습니다.

유일성

모든 간선의 가중치가 서로 다르면 MST는 유일합니다.

MST 관련 변형

최대 신장 트리

간선을 내림차순으로 정렬하면 크루스칼로 최대 신장 트리를 구할 수 있습니다.

JAVA

Arrays.sort(edges, (a, b) -> b[2] - a[2]); // 내림차순 정렬
// 나머지는 크루스칼과 동일

차수 제한 MST

각 정점의 차수가 k 이하인 MST를 구하는 문제입니다. NP-Hard이므로 근사 알고리즘을 사용합니다.

동적 MST

간선이 추가/삭제될 때 MST를 효율적으로 갱신하는 문제입니다.

클러스터링에서의 MST

MST에서 가장 비싼 k-1개의 간선을 제거하면 k개의 클러스터가 됩니다.

JAVA

public static List<Set<Integer>> cluster(int n, int[][] edges, int k) {
    Arrays.sort(edges, Comparator.comparingInt(e -> e[2]));
    UnionFind uf = new UnionFind(n);

    int edgeCount = 0;
    for (int[] edge : edges) {
        if (uf.union(edge[0], edge[1])) {
            edgeCount++;
            if (edgeCount == n - k) break; // V-1-(k-1) = V-k개 간선만 선택
        }
    }

    // 클러스터 추출
    Map<Integer, Set<Integer>> clusters = new HashMap<>();
    for (int i = 0; i < n; i++) {
        clusters.computeIfAbsent(uf.find(i), x -> new HashSet<>()).add(i);
    }
    return new ArrayList<>(clusters.values());
}

백엔드/실무에서의 연결

네트워크 케이블링

데이터센터 내에서 서버 간 네트워크 케이블을 최소 비용으로 연결하는 것은 MST 문제입니다.

분산 시스템의 브로드캐스트 트리

분산 시스템에서 모든 노드에 메시지를 전파할 때, MST를 따라 전파하면 총 전송 비용이 최소화됩니다.

이미지 세그멘테이션

이미지의 픽셀을 노드, 유사도를 간선으로 보면 MST 기반 세그멘테이션이 가능합니다. 비슷한 픽셀끼리 그룹핑됩니다.

근사 알고리즘

TSP(외판원 문제)의 2-근사해를 MST로 구할 수 있습니다. MST의 가중치 합은 항상 TSP 최적해 이하이므로, MST를 기반으로 경로를 구성하면 최적의 2배 이내입니다.

주의할 점

간선 정렬 후 사이클 체크를 빠뜨리는 실수 (크루스칼)

크루스칼 알고리즘에서 간선을 가중치순으로 정렬한 뒤, 선택하려는 간선의 양 끝 노드가 이미 같은 집합인지 Union-Find로 확인해야 합니다. 이 체크를 빠뜨리면 사이클이 생겨 트리가 아닌 그래프가 됩니다.

그래프가 연결되지 않은 경우

MST는 연결 그래프에서만 존재합니다. 연결되지 않은 그래프에서 MST를 구하면 각 컴포넌트별 최소 신장 포레스트가 됩니다.

정리

알고리즘	시간 복잡도	적합한 경우	핵심 자료구조
크루스칼	O(E log E)	희소 그래프	Union-Find
프림 (힙)	O((V+E) log V)	범용	PriorityQueue
프림 (배열)	O(V²)	밀집 그래프	배열

기억할 포인트:

MST는 V개 정점을 V-1개 간선 으로 최소 비용 연결합니다.
크루스칼은 간선 정렬 + Union-Find, 프림은 ** 정점 확장 + 우선순위 큐 **입니다.
Cut Property가 MST 알고리즘의 정당성을 보장합니다.
MST에서 간선을 제거하면 클러스터링이 되고, 이는 실무에서 데이터 그룹핑에 사용됩니다.