[알고리즘 / JAVA] 최소 신장 트리(MST) 완전 정복 – 크루스칼과 프림 알고리즘의 구현과 이해

heon.blog·2025년 6월 11일
알고리즘

알고리즘 / JAVA

목록 보기
8/8
post-thumbnail

1. 개요

복잡한 네트워크를 구성할 때, 어떻게 하면 최소 비용으로 모든 지점을 연결할 수 있을까?
이 문제를 해결하기 위한 핵심 개념이 최소 신장 트리(MST, Minimum Spanning Tree)입니다.
MST는 그래프의 모든 정점을 연결하되, 불필요한 연결 없이 최소 비용만으로 구성된 네트워크를 의미합니다.

이번 포스팅에서는 MST의 개념과 대표적인 알고리즘(크루스칼과 프림), 그리고 실제 구현 방법까지 함께 살펴보겠습니다.

2. MST란?

MST (Minimum Spanning Tree)는 무방향 가중치 그래프에서 모든 정점을 연결하면서, 간선 가중치의 합이 최소가 되도록 구성한 트리를 의미합니다.

조건은 다음과 같습니다:

  • 모든 정점이 연결되어야 함
  • 트리이므로 사이클이 없어야 함
  • 간선 가중치 합이 최소여야 함

MST를 구하는 대표적인 알고리즘으로 크루스칼과 프림 알고리즘이 있습니다.

알고리즘핵심 접근 방식시간 복잡도
크루스칼간선 중심O(E log E)
프림정점 중심O(E log V)

3. MST 구현 방법

3-1. 크루스칼 알고리즘 (Kruskal)

크루스칼 알고리즘은 간선을 중심으로 최소 신장 트리를 만들어 나가는 방식입니다.

우선 모든 간선을 가중치 기준으로 오름차순 정렬한 뒤, 가장 가중치가 작은 간선부터 하나씩 선택하면서 사이클이 생기지 않도록 주의하여 연결합니다.

이때 사이클 여부를 효율적으로 판단하기 위해 유니온 파인드(Union-Find) 자료구조를 사용합니다.

import java.util.*;

public class KruskalMST {
    static int[] parent;

    static class Edge implements Comparable<Edge> {
        int from, to, weight;

        Edge(int from, int to, int weight) { 
            this.from = from;
            this.to = to;
            this.weight = weight;
        }

        @Override
        public int compareTo(Edge other) {
            return this.weight - other.weight;
        }
    }

    static int find(int x) {  
        if (parent[x] == x) return x;
        return parent[x] = find(parent[x]);
    }

    static void union(int a, int b) { 
        int aRoot = find(a);
        int bRoot = find(b);
        if (aRoot != bRoot) {
        	parent[bRoot] = aRoot;
        }
    }

    public static void main(String[] args) {
        int n = 5; // 정점 개수
        List<Edge> edges = Arrays.asList(
            new Edge(1, 2, 3),
            new Edge(1, 3, 2),
            new Edge(2, 3, 1),
            new Edge(2, 4, 4),
            new Edge(3, 5, 6)
        );

        Collections.sort(edges);

        parent = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
        }

        int total = 0;
        for (Edge e : edges) {
            if (find(e.from) != find(e.to)) {
                union(e.from, e.to);
                total += e.weight;
            }
        }

        System.out.println("최소 신장 트리 가중치 합: " + total);
    }
}

다음은 구현 과정입니다.

  1. 그래프의 모든 간선을 모읍니다.
    연결 정보(정점1, 정점2, 가중치)를 간선 리스트에 저장합니다.

  2. 간선들을 가중치 기준으로 오름차순 정렬합니다.
    가장 작은 가중치부터 하나씩 선택할 수 있도록 정렬합니다.

  3. 유니온-파인드(Disjoint Set)를 준비합니다.
    각각의 정점이 자신을 부모로 갖도록 초기화하여, 나중에 사이클 여부를 빠르게 판단할 수 있게 합니다.

  4. 정렬된 간선을 하나씩 보면서, 두 정점이 연결되어 있지 않다면 연결합니다.
    이때 서로 다른 집합에 속해 있는지(= 사이클이 생기지 않는지)를 find()로 확인합니다. 연결해도 괜찮다면 union()을 통해 합칩니다.

  5. 간선을 연결할 때마다 가중치를 누적합니다.
    최종적으로 모든 정점을 연결하게 되면, 누적된 가중치 합이 바로 최소 신장 트리의 비용입니다.

3-2. 프림 알고리즘 (Prim)

프림 알고리즘은 정점을 중심으로 최소 신장 트리를 확장해 나가는 방식입니다.

처음에 아무 정점 하나에서 시작해서, 현재 방문한 정점과 인접한 간선 중 가장 작은 것을 선택해 트리에 포함시킵니다. 이를 반복하여 모든 정점이 연결될 때까지 진행합니다.

우선순위 큐(PriorityQueue)를 사용하여 가장 가중치가 작은 간선을 빠르게 선택합니다.

import java.util.*;

public class PrimMST {
    static class Node implements Comparable<Node> {
        int to, weight;

        Node(int to, int weight) {
            this.to = to;
            this.weight = weight;
        }

        @Override
        public int compareTo(Node other) {
            return this.weight - other.weight;
        }
    }

    public static void main(String[] args) {
        int n = 5;
        List<List<Node>> graph = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            graph.add(new ArrayList<>());
        }

        // 무방향 간선 추가
        graph.get(1).add(new Node(2, 3));
        graph.get(2).add(new Node(1, 3));
        graph.get(1).add(new Node(3, 2));
        graph.get(3).add(new Node(1, 2));
        graph.get(2).add(new Node(3, 1));
        graph.get(3).add(new Node(2, 1));
        graph.get(2).add(new Node(4, 4));
        graph.get(4).add(new Node(2, 4));
        graph.get(3).add(new Node(5, 6));
        graph.get(5).add(new Node(3, 6));

        boolean[] visited = new boolean[n + 1];
        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.add(new Node(1, 0));

        int total = 0;
        while (!pq.isEmpty()) {
            Node current = pq.poll();
            if (visited[current.to]) continue;
            visited[current.to] = true;
            total += current.weight;

            for (Node next : graph.get(current.to)) {
                if (!visited[next.to]) {
                    pq.add(next);
                }
            }
        }

        System.out.println("최소 신장 트리 가중치 합: " + total);
    }
}

다음은 구현 과정입니다.

  1. 인접 리스트 형태로 그래프를 구성합니다.
    각 정점마다 연결된 간선들을 저장합니다. 무방향 그래프이므로 양쪽 모두 추가합니다.

  2. 임의의 시작 정점을 정하고, 우선순위 큐에 넣습니다.
    처음에는 연결된 간선이 없으므로 가중치 0으로 시작 정점을 큐에 넣습니다.

  3. 우선순위 큐에서 가장 가중치가 작은 간선을 꺼냅니다.
    만약 해당 정점이 이미 방문된 정점이라면 무시하고, 아니라면 방문 처리합니다.

  4. 선택된 간선의 가중치를 누적하고, 해당 정점에서 뻗어나가는 모든 간선을 큐에 추가합니다.
    단, 아직 방문하지 않은 정점들만 대상으로 합니다.

  5. 모든 정점을 방문할 때까지 반복합니다.
    우선순위 큐가 빌 때까지 진행하면, 최소 신장 트리의 비용이 완성됩니다.

4. MST vs 다익스트라 vs 플로이드-워셜

항목MST다익스트라플로이드-워셜
목적최소 연결 비용단일 시작점 최단 거리모든 정점 쌍 최단 거리
방향성무방향 그래프방향 그래프 가능방향 그래프 가능
음수 가중치불가 (사이클 없이 양수만)불가가능
기술 방식크루스칼/프림 (Union-Find, PQ)우선순위 큐 (힙)3중 for문
시간 복잡도O(E log E), O(E log V)O((V + E) log V)O(V³)

5. 백준 문제 추천

사이트문제 번호 / 제목설명
백준 1197최소 스패닝 트리MST 기본 구현 문제
백준 1922네트워크 연결MST 구현 문제
백준 1647도시 분할 계획MST 응용 문제
백준 4386별자리 만들기좌표 기반 + MST

6. 마무리

최소 신장 트리는 여러 지점을 가장 효율적으로 연결하는 과정입니다.
불필요한 연결을 줄이고, 꼭 필요한 간선만으로 전체를 하나로 묶는 것이 핵심이죠.
모든 노드를 최소 비용으로 연결해야 하는 상황에서 반드시 알아야 할 개념입니다.

MST를 구하는 방법에는 앞서 다룬 것처럼,
크루스칼 알고리즘에서 간선을 중심으로 확장하는 방법과
프림 알고리즘에서 정점을 중심으로 확장하는 방법이 있습니다.
그래프의 구조와 조건에 따라 더 적합한 알고리즘을 선택하는 것이 중요합니다.

profile
heon.blog
유익한 글을 목표로 하는 공간입니다.
이전 포스트

[알고리즘 / JAVA] 유니온 파인드(Union-Find) 완전 정복 – 집합의 연결 관계 이해

0개의 댓글