[알고리즘] 최소 신장 트리 MST

Minimum Spanning Tree (MST)

무방향 그래프에서 간선의 비용을 최소로 하는 사이클이 없는 트리이다.
N개의 정점을 연결하는 N-1개의 간선을 선택한다.
MST를 구하는 알고리즘에는 크루스칼(Kruskal) 알고리즘, 프림(Prim) 알고리즘이 있다.
크루스칼 알고리즘은 간선을 중심으로 MST를 구하는 알고리즘이고,
프림 알고리즘은 정점을 중심으로 MST를 구하는 알고리즘이다.

배경 지식 : union-find

유니온 파인드

예제 문제

https://www.acmicpc.net/problem/1197

크루스칼 알고리즘

• 간선이 많은 밀집된 그래프에서 사용한다.
• 모든 간선을 가중치 기준으로 오름차순 정렬하고, 순서대로 간선을 선택하여 MST를 완성한다.
  이때, union-find를 이용하여 이미 트리에 포함된 정점인지 (사이클이 존재하는지) 확인한다.

코드

정점 두 개와 간선의 정보를 담은 클래스

public static class Graph{
    int vtx1, vtx2, val;

    public Graph(int vtx1, int vtx2, int val){
        this.vtx1 = vtx1;
        this.vtx2 = vtx2;
        this.val = val;
    }
}

Graph 클래스를 담을 리스트와, 간선을 기준으로 오름차순 정렬

List<Graph> partialGraph = new ArrayList<>();

Collections.sort(partialGraph, new Comparator<Graph>() {
        @Override
        public int compare(Graph o1, Graph o2){
            return o1.val - o2.val;
        }
});

union(트리 생성) - find(트리에 속해 있는지 확인)

public static int find(int[] parent, int num){
    if(parent[num] == num) return num;
    else return find(parent, parent[num]);
}

public static void union(int[] parent, int x, int y){
    x = find(parent, x);
    y = find(parent, y);

    int min = Math.min(x, y);

    parent[x] = min;
    parent[y] = min;
}

모든 간선을 순서대로 탐색하면서 (두 정점이 연결돼있는 부분 그래프를 탐색하면서)
트리에 연결돼있지 않으면 트리에 추가

int valSum = 0;
for(Graph graph : partialGraph){

    // 이미 트리에 연결돼있으면 pass
    if(find(parent, graph.vtx1) == find(parent, graph.vtx2)) continue;

    union(parent, graph.vtx1, graph.vtx2);
    valSum += graph.val;
}

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

// 크루스컬 -> 간선을 오름차순 정렬
public class Main {

    public static class Graph{
        int vtx1, vtx2, val;

        public Graph(int vtx1, int vtx2, int val){
            this.vtx1 = vtx1;
            this.vtx2 = vtx2;
            this.val = val;
        }
    }

    public static int find(int[] parent, int num){
        if(parent[num] == num) return num;
        else return find(parent, parent[num]);
    }

    public static void union(int[] parent, int x, int y){
        x = find(parent, x);
        y = find(parent, y);

        int min = Math.min(x, y);

        parent[x] = min;
        parent[y] = min;
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());
        int vtxSize = Integer.parseInt(stringTokenizer.nextToken());
        int edgeSize = Integer.parseInt(stringTokenizer.nextToken());

        List<Graph> partialGraph = new ArrayList<>();
        int[] parent = new int[vtxSize + 1];
        for(int i = 0; i <= vtxSize; i++){
            parent[i] = i;
        }

        for(int i = 0; i < edgeSize; i++){
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            int vtx1 = Integer.parseInt(stringTokenizer.nextToken());
            int vtx2 = Integer.parseInt(stringTokenizer.nextToken());
            int val = Integer.parseInt(stringTokenizer.nextToken());

            partialGraph.add(new Graph(vtx1, vtx2, val));
        }
        
        // 가중치 (val) 기준으로 오름차순 정렬
        Collections.sort(partialGraph, new Comparator<Graph>() {
            @Override
            public int compare(Graph o1, Graph o2){
                return o1.val - o2.val;
            }
        });

        int valSum = 0;
        for(Graph graph : partialGraph){

            // 이미 트리에 연결돼있으면 pass
            if(find(parent, graph.vtx1) == find(parent, graph.vtx2)) continue;

            union(parent, graph.vtx1, graph.vtx2);
            valSum += graph.val;
        }

        System.out.println(valSum);
    }
}

프림 알고리즘

• 정점이 많은 희소 그래프에서 사용한다.
• 현재까지 연결된 정점에 연결된 정점 중, 트리에 포함되지 않고 간선의 가중치가 가장 작은 정점을 연결한다.
  이때, 우선순위 큐를 이용하고, union-find를 이용하여 이미 트리에 포함된 정점인지 (사이클이 존재하는지) 확인한다.