[알고리즘] MST

 

1. MST 란? 

최소 신장 트리는 연결 그래프의 부분 그래프로, 그래프의 모든 정점을 포함하면서 간선의 총 가중치가 최소가 되는 트리

( 네트워크 설계, 클러스터링, 그래픽스 등 사용 )

 

• 연결 그래프: 모든 정점이 서로 연결되어 있는 그래프
• 트리: 사이클이 없는 그래프
• 신장 트리: 그래프의 모든 정점을 포함하는 트리
• 최소 신장 트리: 신장 트리 중 간선 가중치의 합이 최소인 트리

 

2. 구현 방법

 

1. 크루스칼 알고리즘

  - 모든 간선을 가중치 기준으로 정렬합니다.

 

  - 가장 작은 가중치의 간선부터 차례대로 선택하여 MST에 추가

 

  - 간선을 추가할 때, 사이클이 발생하지 않도록 유니온-파인드(Union-Find) 자료구조를 사용하여 관리

 

시간 복잡도: O(E log E), E: 간선의 수

장점: 구현이 간단하고, 간선의 수가 적을 때 효율적

 

import java.util.*;

class Edge implements Comparable<Edge> {
    int src, dest, weight;

    public int compareTo(Edge edge) {
        return this.weight - edge.weight;
    }
}

class DisjointSet {
    int[] parent, rank;

    public DisjointSet(int n) {
        parent = new int[n];
        rank = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 0;
        }
    }

    public int find(int u) {
        if (u != parent[u]) {
            parent[u] = find(parent[u]);
        }
        return parent[u];
    }

    public void union(int u, int v) {
        int rootU = find(u);
        int rootV = find(v);
        if (rootU != rootV) {
            if (rank[rootU] > rank[rootV]) {
                parent[rootV] = rootU;
            } else if (rank[rootU] < rank[rootV]) {
                parent[rootU] = rootV;
            } else {
                parent[rootV] = rootU;
                rank[rootU]++;
            }
        }
    }
}

public class KruskalMST {
    public static void main(String[] args) {
        int V = 4;
        Edge[] edges = new Edge[] {
            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)
        };

        Arrays.sort(edges);

        DisjointSet ds = new DisjointSet(V);
        List<Edge> mst = new ArrayList<>();

        for (Edge edge : edges) {
            int u = edge.src;
            int v = edge.dest;

            if (ds.find(u) != ds.find(v)) {
                ds.union(u, v);
                mst.add(edge);
            }
        }

        System.out.println("최소 신장 트리의 간선:");
        for (Edge edge : mst) {
            System.out.println(edge.src + " -- " + edge.dest + " == " + edge.weight);
        }
    }
}

 

 

2. 프림 알고리즘

  - 시작 정점을 선택하여 MST에 포함

 

  - MST에 포함된 정점과 연결된 간선 중 가중치가 가장 작은 간선을 선택하여 MST에 추가

 

  - 모든 정점이 MST에 포함될 때까지 반복

 

시간 복잡도: O(E log V), V : 정점의 수 (우선순위 큐를 사용하면 더욱 효율적으로 구현 가능)

장점: dense graph(간선이 많은 그래프)에서 효과적

 

import java.util.*;

class Edge {
    int dest, weight;

    public Edge(int dest, int weight) {
        this.dest = dest;
        this.weight = weight;
    }
}

public class PrimMST {
    public static void main(String[] args) {
        int V = 5; 
        List<List<Edge>> graph = new ArrayList<>();

        for (int i = 0; i < V; i++) graph.add(new ArrayList<>());
        

        // 양방향 간선 추가
        graph.get(0).add(new Edge(1, 2));
        graph.get(1).add(new Edge(0, 2)); 
        graph.get(0).add(new Edge(3, 6));
        graph.get(3).add(new Edge(0, 6)); 
        graph.get(1).add(new Edge(2, 3));
        graph.get(2).add(new Edge(1, 3)); 
        graph.get(1).add(new Edge(3, 8));
        graph.get(3).add(new Edge(1, 8)); 
        graph.get(1).add(new Edge(4, 5));
        graph.get(4).add(new Edge(1, 5));
        graph.get(2).add(new Edge(4, 7));
        graph.get(4).add(new Edge(2, 7)); 
        graph.get(3).add(new Edge(4, 9));
        graph.get(4).add(new Edge(3, 9));

        primMST(graph, V);
    }

    public static void primMST(List<List<Edge>> graph, int V) {
        boolean[] inMST = new boolean[V]; // MST에 포함된 정점 여부
        Edge[] edgeTo = new Edge[V];
        int[] minWeight = new int[V]; // 최소 가중치
        Arrays.fill(minWeight, Integer.MAX_VALUE); // 초기화
        minWeight[0] = 0;

        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a[1]));
        pq.offer(new int[]{0, 0});

        while (!pq.isEmpty()) {
            int[] current = pq.poll();
            int u = current[0];

            if (inMST[u]) continue;
            inMST[u] = true; 

            for (Edge edge : graph.get(u)) {
                int v = edge.dest;
                int weight = edge.weight;

                if (!inMST[v] && weight < minWeight[v]) {
                    minWeight[v] = weight;
                    edgeTo[v] = edge;
                    pq.offer(new int[]{v, weight});
                }
            }
        }

        // 결과 출력
        System.out.println("최소 신장 트리의 간선:");
        for (int i = 1; i < V; i++) {
            if (edgeTo[i] != null) {
                System.out.println(edgeTo[i].dest + " -- " + (edgeTo[i].weight) + " (가중치: " + minWeight[i] + ")");
            }
        }
    }
}