최소 신장 트리(Minimum Spanning Tree, MST)는 그래프에서 모든 정점을 포함하면서 사이클이 없는 부분 그래프 중에서 간선의 가중치 합이 최소인 트리를 말합니다. 이 트리는 주로 네트워크 연결, 도로 건설, 회로 설계 등 다양한 분야에서 활용됩니다.

주요한 최소 신장 트리 알고리즘으로는 프림 알고리즘(Prim's Algorithm)과 크루스칼 알고리즘(Kruskal's Algorithm)이 있습니다. 각각의 알고리즘은 서로 다른 접근 방식을 가지고 있지만, 모두 최소 신장 트리를 찾는 데 사용됩니다.

프림 알고리즘(Prim's Algorithm)

• 한 정점을 시작으로 선택하고, 해당 정점과 연결된 간선 중 가장 가중치가 작은 간선을 선택하여 트리를 확장해 나갑니다.
• 선택된 간선으로 연결된 정점들 중에서 아직 트리에 포함되지 않은 정점으로 확장합니다.
• 모든 정점이 트리에 포함될 때까지 위 과정을 반복하며, 최소 신장 트리를 구축합니다.

크루스칼 알고리즘(Kruskal's Algorithm)

• 모든 간선을 가중치의 오름차순으로 정렬합니다.
• 가장 가중치가 작은 간선부터 선택하며, 해당 간선을 추가했을 때 사이클이 생기지 않는 경우에만 트리에 추가합니다.
• 모든 간선에 대해 위 과정을 반복하며, 최소 신장 트리를 구축합니다.

시간 복잡도

프림 알고리즘의 시간 복잡도는 O(V^2) 또는 O(ElogV)입니다. (V는 정점의 수, E는 간선의 수)
크루스칼 알고리즘의 시간 복잡도는 O(ElogE) 또는 O(ElogV)입니다.

구현 방법 및 예제

// 알고리즘 - 최소 신장 트리
// 크루스칼 알고리즘

import java.util.Arrays;

public class Main {
    static int[] parents;

    public static int kruskal(int[][] data, int v, int e) {
        int weightSum = 0;

        Arrays.sort(data, (x, y) -> x[2] - y[2]);

        parents = new int[v + 1];
        for (int i = 1; i < v + 1; i++) {
            parents[i] = i;
        }

        for (int i = 0; i < e; i++) {
            if(find(data[i][0]) != find(data[i][1])){
                union(data[i][0], data[i][1]);
                weightSum += data[i][2];
            }
        }

        return weightSum;
    }

    public static void union(int a, int b){
        int aP = find(a);
        int bP = find(b);

        if(aP != bP){
            parents[aP] = bP;
        }
    }

    public static int find(int a){
        if(a == parents[a]){
            return a;
        }
        return parents[a] = find(parents[a]);
    }

    public static void main(String[] args) {
        int v = 7;
        int e = 10;
        int[][] graph = {{1, 3, 1}, {1, 2, 9}, {1, 6, 8}, {2, 4, 13}, {2, 5, 2}, {2, 6, 7}, {3, 4, 12}, {4, 7, 17}, {5, 6, 5}, {5, 7, 20}};

        System.out.println(kruskal(graph, v, e));
    }
}

// 프림 알고리즘

import java.util.ArrayList;
import java.util.PriorityQueue;

public class Main2 {

    static class Node{
        int to;
        int weight;

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

    public static int prim(int[][] data, int v, int e) {
        int weightSum = 0;

        ArrayList<ArrayList<Node>> graph = new ArrayList<>();
        for (int i = 0; i < v + 1; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 0; i < e; i++) {
            graph.get(data[i][0]).add(new Node(data[i][1], data[i][2]));
            graph.get(data[i][1]).add(new Node(data[i][0], data[i][2]));
        }

        boolean[] visited = new boolean[v + 1];
        PriorityQueue<Node> pq = new PriorityQueue<>((x, y) -> x.weight - y.weight);
        pq.add(new Node(1, 0));

        int cnt = 0;
        while(!pq.isEmpty()){
            Node cur = pq.poll();
            cnt += 1;

            if(visited[cur.to]){
                continue;
            }
            visited[cur.to] = true;
            weightSum += cur.weight;

            if(cnt == v){
                return weightSum;
            }

            for (int i = 0; i < graph.get(cur.to).size(); i++) {
                Node adjNode = graph.get(cur.to).get(i);
                if(visited[adjNode.to]){
                    continue;
                }
                pq.offer(adjNode);
            }
        }
        return weightSum;
    }

    public static void main(String[] args) {
        int v = 7;
        int e = 10;
        int[][] graph = {{1, 3, 1}, {1, 2, 9}, {1, 6, 8}, {2, 4, 13}, {2, 5, 2}, {2, 6, 7}, {3, 4, 12}, {4, 7, 17}, {5, 6, 5}, {5, 7, 20}};

        System.out.println(prim(graph, v, e));
    }
}