MST 에 관하여

최소 신장 트리(MST, Minimum Spanning Tree)는 그래프 내의 모든 정점을 연결하는 최소 비용의 간선 집합으로 이루어진 트리를 의미합니다. 즉, 그래프의 모든 노드를 최소 비용으로 연결하는 것입니다.

---

1. MST의 특징

• 모든 정점이 연결되어 있어야 합니다.
• 사이클을 포함해서는 안 됩니다.
• 최소한의 비용으로 구성됩니다.

---

2. MST 알고리즘 종류

최소 신장 트리를 구하는 대표적인 알고리즘은 다음과 같습니다.

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

• 시간 복잡도: O(ElogE)
• 간선의 비용을 기준으로 오름차순으로 정렬한 후, 사이클을 형성하지 않도록 최소 비용 간선을 순차적으로 선택합니다.

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

• 시간 복잡도: O(ElogV)
• 시작 정점에서부터 시작하여 연결된 정점들 중 최소 비용의 간선을 선택하여 확장하는 방식입니다.

---

3. 크루스칼 알고리즘 구현(Java)

import java.util.*;

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

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

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

class DisjointSet {
    int[] parent;

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

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

    void union(int x, int y) {
        int xRoot = find(x);
        int yRoot = find(y);
        parent[yRoot] = xRoot;
    }
}

public class KruskalMST {
    static List<Edge> kruskalMST(List<Edge> edges, int V) {
        Collections.sort(edges);
        DisjointSet ds = new DisjointSet(V);

        List<Edge> result = new ArrayList<>();
        int e = 0;

        for (Edge edge : edges) {
            int x = ds.find(edge.src);
            int y = ds.find(edge.dest);

            if (x != y) {
                result.add(edge);
                ds.union(x, y);
                e++;
                if (e == V - 1) break;
            }
        }
        return result;
    }
}

public class Main {
    public static void main(String[] args) {
        int V = 4;
        List<Edge> edges = new ArrayList<>();

        edges.add(new Edge(0, 1, 10));
        edges.add(new Edge(0, 2, 6));
        edges.add(new Edge(0, 3, 5));
        edges.add(new Edge(1, 3, 15));
        edges.add(new Edge(2, 3, 4));

        List<Edge> result = KruskalMST.kruskalMST(edges, V);

        int minimumCost = 0;
        for (Edge edge : result) {
            System.out.println(edge.src + " - " + edge.dest + ": " + edge.weight);
            minimumCost += edge.weight;
        }

        System.out.println("최소 비용: " + minimumCost);
    }
}

---

4. 마무리

최소 신장 트리 알고리즘은 최소 비용으로 모든 노드를 연결하는 효율적인 방법으로, 다양한 현실 문제 해결에 널리 활용됩니다. 다음과 같은 분야에서 활용됩니다.

• 네트워크 설계 및 구축
• 전력 공급망 최적화
• 도시 계획 및 도로망 구축