[알고리즘] 최소 신장 트리(MST) : 크루스칼 알고리즘, 프림 알고리즘

최소 신장 트리(MST)의 크루스칼(Kruskal) 알고리즘과 프림(Prim) 알고리즘에 대해 공부 후 정리하였습니다.

1. 최소 신장 트리 (MST: Minimum Spanning Tree)

1️⃣ 개념

• 신장 트리(Spanning Tree)
  • 그래프의 모든 정점을 포함
  • 간선 수 = 정점 수 - 1
  • 사이클이 없음
• 최소 신장 트리
  • 가능한 모든 신장 트리 중 간선 가중치의 합이 최소인 트리
• 조건
  • 무방향, 가중치 그래프
  • 연결 그래프 (모든 정점이 연결되어 있어야 함)

2️⃣ MST 구하는 방법

• 크루스칼(Kruskal) → 간선 중심, 정렬 + Union-Find
• 프림(Prim) → 정점 중심, 우선순위 큐

2. 크루스칼 알고리즘 (Kruskal)

1️⃣ 개념

간선을 가중치 오름차순으로 정렬 후, 가장 작은 간선부터 사이클이 생기지 않도록 선택
Union-Find으로 사이클 판별
대표적인 그리디(Greedy) 알고리즘

2️⃣ 특징

• 간선 중심 (Edge-based)
• 유니온 파인드(Disjoint Set) 자료구조를 사용
• 모든 간선을 정렬 → 사이클 검사하며 선택
• 간선이 적은 희소 그래프(Sparse Graph)에서 유리

3️⃣ 시간 복잡도

• O(E log E) (E는 간선 수) → 정렬에 걸리는 시간
• 유니온 파인드는 거의 상수 시간 (O(α(N)))

4️⃣ 구현 절차

1. 모든 간선을 가중치 기준 오름차순 정렬
2. Union-Find 초기화
3. 가중치가 가장 작은 간선 선택 후
   1. 두 정점이 같은 집합이면 무시
   2. 다른 집합이면 같은 그룹으로 만들고, MST에 간선 추가
4. N-1개의 간선 선택 시 종료, 아니라면 3번 과정 반복

5️⃣ 기본 코드

import java.util.*;

class Edge implements Comparable<Edge> {
    int u, v, weight;

    Edge(int u, int v, int weight) {
        this.u = u;
        this.v = v;
        this.weight = weight;
    }

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

class UnionFind {
    int[] parent;

    UnionFind(int size) {
        parent = new int[size];
        for (int i = 0; i < size; i++)
            parent[i] = i;
    }

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

    boolean union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) return false;
        parent[rootY] = rootX;
        return true;
    }
}

public class KruskalMST {
    public static int kruskal(int V, List<Edge> edges) {
        Collections.sort(edges); // 간선 가중치 기준 정렬
        UnionFind uf = new UnionFind(V);
        int totalWeight = 0;

        for (Edge edge : edges) {
            if (uf.union(edge.u, edge.v)) {
                totalWeight += edge.weight;
            }
        }

        return totalWeight;
    }

    public static void main(String[] args) {
        int V = 4;
        List<Edge> edges = new ArrayList<>();
        edges.add(new Edge(0, 1, 1));
        edges.add(new Edge(1, 2, 4));
        edges.add(new Edge(0, 2, 3));
        edges.add(new Edge(2, 3, 2));
        edges.add(new Edge(1, 3, 5));

        System.out.println("Minimum Spanning Tree Weight: " + kruskal(V, edges));
    }
}

유니온 파인드를 클래스로 분리하지 않은 코드

import java.util.*;

class Edge implements Comparable<Edge> {
int u, v, weight;
Edge(int u, int v, int weight) {
this.u = u; this.v = v; this.weight = weight;
}
@Override
public int compareTo(Edge o) {
return this.weight - o.weight;
}
}

public class KruskalMST {
static int[] parent;

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

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

    public static void main(String[] args) {
        int V = 4;
        int E = 5;
        List<Edge> edges = Arrays.asList(
            new Edge(0, 1, 10),
            new Edge(0, 2, 6),
            new Edge(0, 3, 5),
            new Edge(1, 3, 15),
            new Edge(2, 3, 4)
        );

        Collections.sort(edges); // 간선 정렬
        parent = new int[V];
        for (int i = 0; i < V; i++) parent[i] = i;

        int mstWeight = 0;
        for (Edge edge : edges) {
            if (find(edge.u) != find(edge.v)) {
                union(edge.u, edge.v);
                mstWeight += edge.weight;
            }
        }

        System.out.println("MST 가중치 합: " + mstWeight);
    }

}

3. 프림 알고리즘 (Prim)

1️⃣ 개념

임의의 시작 정점에서 시작 → MST에 속하지 않은 정점 중 최소 가중치 간선을 선택하며 확장
그리디 방식

2️⃣ 특징

• 정점 중심 (Vertex-based)
• 우선순위 큐(PriorityQueue)를 사용하여 가장 작은 간선을 선택
• 간선이 많은 밀집 그래프(Dense Graph)에서 유리
• BFS와 비슷하게 동작하지만, 간선 선택 기준이 다름

3️⃣ 시간 복잡도

O(E log V) (우선순위 큐 사용 시)

4️⃣ 구현 절차

1. 임의의 시작 정점 선택 후 MST에 추가
2. 해당 정점과 연결된 간선들을 우선순위 큐에 넣기
3. 우선순위 큐에서 최소 가중치 간선을 꺼내기
   1. 해당 간선이 MST에 포함된 두 정점을 연결하면 continue
   2. 연결된 정점이 MST에 없으면 추가
4. 새로 추가된 정점에서 연결된 간선을 우선순위 큐에 넣기
5. 모든 정점이 MST에 포함될 때까지 3 ~ 4 과정 반복

5️⃣ 기본 코드

import java.util.*;

class PrimEdge implements Comparable<PrimEdge> {
    int to, weight;
    PrimEdge(int to, int weight) {
        this.to = to; this.weight = weight;
    }
    @Override
    public int compareTo(PrimEdge o) {
        return this.weight - o.weight;
    }
}

public class PrimMST {
    public static void main(String[] args) {
        int V = 4;
        List<List<PrimEdge>> graph = new ArrayList<>();
        for (int i = 0; i < V; i++) graph.add(new ArrayList<>());

        // 무방향 간선 추가
        graph.get(0).add(new PrimEdge(1, 10));
        graph.get(1).add(new PrimEdge(0, 10));

        graph.get(0).add(new PrimEdge(2, 6));
        graph.get(2).add(new PrimEdge(0, 6));

        graph.get(0).add(new PrimEdge(3, 5));
        graph.get(3).add(new PrimEdge(0, 5));

        graph.get(1).add(new PrimEdge(3, 15));
        graph.get(3).add(new PrimEdge(1, 15));

        graph.get(2).add(new PrimEdge(3, 4));
        graph.get(3).add(new PrimEdge(2, 4));

        boolean[] visited = new boolean[V];
        PriorityQueue<PrimEdge> pq = new PriorityQueue<>();
        pq.offer(new PrimEdge(0, 0)); // 시작 정점(0), 가중치 0

        int mstWeight = 0;
        while (!pq.isEmpty()) {
            PrimEdge current = pq.poll();
            if (visited[current.to]) continue;

            visited[current.to] = true;
            mstWeight += current.weight;

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

        System.out.println("MST 가중치 합: " + mstWeight);
    }
}

클래스로 분리한 동일 코드

import java.util.*;

class Node implements Comparable<Node> {
int vertex, weight;

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

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

}

public class PrimMST {
public static int prim(int V, List<List<Node>> graph) {
boolean[] visited = new boolean[V];
PriorityQueue<Node> pq = new PriorityQueue<>();
pq.offer(new Node(0, 0)); // 시작 정점
int totalWeight = 0;

        while (!pq.isEmpty()) {
            Node cur = pq.poll();

            if (visited[cur.vertex]) continue;
            visited[cur.vertex] = true;
            totalWeight += cur.weight;

            for (Node neighbor : graph.get(cur.vertex)) {
                if (!visited[neighbor.vertex]) {
                    pq.offer(new Node(neighbor.vertex, neighbor.weight));
                }
            }
        }

        return totalWeight;
    }

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

        graph.get(0).add(new Node(1, 1));
        graph.get(0).add(new Node(2, 3));
        graph.get(1).add(new Node(0, 1));
        graph.get(1).add(new Node(2, 4));
        graph.get(1).add(new Node(3, 5));
        graph.get(2).add(new Node(0, 3));
        graph.get(2).add(new Node(1, 4));
        graph.get(2).add(new Node(3, 2));
        graph.get(3).add(new Node(1, 5));
        graph.get(3).add(new Node(2, 2));

        System.out.println("Minimum Spanning Tree Weight: " + prim(V, graph));
    }

}

4. 비교

구분	크루스칼(Kruskal)	프림(Prim)
중심	간선 중심	정점 중심
자료구조	간선 리스트 + 정렬 + Union-Find	인접 리스트 + 우선순위 큐
시간 복잡도	O(E log E)	O(E log V)
유리한 경우	희소 그래프	밀집 그래프
구현 난이도	중간 (Union-Find 필요)	중간 (PriorityQueue 필요)