Minimal Spanning Tree (최소 신장 트리)

1. 최소 신장 트리 (MST)

• MST : Minimum Spanning Tree
• 그래프 상의 모든 노드들을 최소 비용으로 연결하는 방법
  • 크루스칼, 프림

2. 크루스칼 알고리즘

• 간선 중 최소 값을 가진 간선부터 연결
• 사이클 발생 시 다른 간선 선택
• 주로 간선 수가 적을 때 사용
• O(E logE)

⇒ 총 비용 : 45

• 사이클 발생 체크 방법 (Union-Find)

(실습 : 크루스칼 알고리즘)

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

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) {
        // Test code
        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));
    }
}

3. 프림 알고리즘

• 임의의 노드에서 시작
• 연결된 노드들의 간선 중 낮은 가중치를 갖는 간선 선택
• 간선의 갯수가 많을 때 크루스칼보다 유리
• O(E logV) → E: 간선 수, V : 정점 수

(실습 : 프림 알고리즘)

// 프림 알고리즘

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++;

            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) {
        // Test code
        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));
    }
}