최소 신장 트리(MST)

최소 신장 트리란?

그래프의 모든 정점을 사이클 없이 잇는 트리에서 간선의 가중치의 합이 최소가 되는 트리

• 그래프에서 최소 비용 문제
  1. 모든 정점을 연결하는 간선들의 가중치의 합이 최소
  2. 두 정점 사이의 최소 비용의 경로 찾기
• 신장 트리
  n개의 정점으로 이루어진 무향 그래프에서 n개의 정점과 n-1개의 간선으로 이루어진 트리
  -> 최소 신장 트리 (Minimum Spanning Tree)는 가중치의 합이 최소인 신장 트리 !

그러면 어떻게 구할 수 있을까?

• 간선 중심으로 최소 신장트리를 구하자
• 한 정점에서 하나의 간선은 무조건 존재하므로 정점에서 최소인 것을 연결 (?)

바로 이 두 방법이 유명한 MST알고리즘인 KRUSKAL 알고리즘과 PRIM 알고리즘이다.

KRUSKAL 알고리즘 (크루스칼 알고리즘)

간선 중심으로 최소 신장 트리를 구하는 알고리즘

• 간선이 적다면 유리.

방법

1. 최초, 모든 간선을 가중치에 따라 오름차순 정렬
2. 그 중 가장 가중치가 작은 간선부터 선택
   2-1. 사이클이 존재 ? 해당 간선을 제외, 그 다음으로 낮은 간선 선택
3. n-1개가 될 때까지 반복

※ 사이클 여부는 어떻게 확인 ? Union-Find를 사용하자

BOJ1922_네트워크 연결

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    static int N;
    static int[] p;
    static class Node implements Comparable<Node>{
        int a;
        int b;
        int cost;
        public Node(int a, int b, int cost) {
            this.a = a;
            this.b = b;
            this.cost = cost;
        }
        @Override
        public int compareTo(Node o) {
            return cost - o.cost;
        }
    }
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader((new InputStreamReader(System.in)));
        N = Integer.parseInt(br.readLine());
        int M = Integer.parseInt(br.readLine());

        p = new int[N+1];
        for (int i = 0; i <= N; i++) p[i] = i;

        PriorityQueue<Node> pq = new PriorityQueue<>();
        for (int i = 0; i < M; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            pq.offer(new Node(a, b, cost));
        }
        int edgeCnt = 0;
        int ans = 0;
        while (edgeCnt != N-1) {
            Node now = pq.poll();
            if (union(now.a, now.b)) {
                edgeCnt++;
                ans += now.cost;
            }
        }
        System.out.println(ans);
        br.close();
    }
    static boolean union(int x, int y) {
        int pX = find(x);
        int pY = find(y);

        if (pX == pY) return false;

        if (pX < pY) p[pX] = pY;
        else p[pY] = pX;
        return true;
    }
    static int find(int x) {
        if (p[x] == x) return x;
        return p[x] = find(p[x]);
    }
}

PRIM 알고리즘

정점 중심으로 최소 신장 트리를 구하는 알고리즘

• 정점이 적다면 유리.

방법

1. 임의의 정점 선택
2. 선택한 정점과 인접하는 정점들 중의 최소 비용의 간선이 존재하는 정점을 선택
3. 그 간선이 연결하는 정점 선택, 모든 정점이 선택될 때까지 2과정 반복

BOJ6497_전력난

package blog;

import java.io.BufferedReader;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class MST_Prim {
    static class Edge {
        int to;
        int cost;
        public Edge(int to, int cost) {
            this.to = to;
            this.cost = cost;
        }
    }
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        while (true) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int m = Integer.parseInt(st.nextToken());
            int n = Integer.parseInt(st.nextToken());
            if (m == 0 && n == 0) break;
            ArrayList<ArrayList<Edge>> edgeList = new ArrayList<>();
            for (int i = 0; i < m; i++) edgeList.add(new ArrayList<>());

            PriorityQueue<Edge> pq = new PriorityQueue<>((o1, o2)->(o1.cost-o2.cost));
            int total = 0;
            for (int i = 0; i < n; i++) {
                st = new StringTokenizer(br.readLine());
                int a = Integer.parseInt(st.nextToken());
                int b = Integer.parseInt(st.nextToken());
                int cost = Integer.parseInt(st.nextToken());
                edgeList.get(a).add(new Edge(b, cost));
                edgeList.get(b).add(new Edge(a, cost));
                total += cost;
            }

            boolean[] isVisited = new boolean[m];
            int useCost = 0;
            pq.offer(new Edge(0, 0));
            while(!pq.isEmpty()) {
                Edge now = pq.poll();
                if (isVisited[now.to]) continue;
                isVisited[now.to] = true;
                useCost += now.cost;

                for (Edge edge : edgeList.get(now.to)) {
                    if (!isVisited[edge.to]) pq.offer(edge);
                }
            }
            sb.append(total-useCost).append("\n");
        }
        System.out.print(sb);
        br.close();
    }
}