[그래프/개념] 최소 스패닝 트리(Minimum Spanning Tree), 크루스칼 알고리즘

트리 : 연결그래프이며 정점의 개수가 N개 일 때, 간선의 개수가 N-1인 트리

스패닝트리 : 신장트리, 무향 연결 그래프가 있을 때 그 그래프에서 간선을 부분적으로 뽑아서 만들 수 있는,

그래프의 정점 개수와 같은 정점 개수를 가지는 트리

최소 스패닝 트리 (MST) : 트리의 간선마다 가중치(cost)가 있을 때, 간선의 가중치 합이 최소인 트리

하나의 그래프에 대해 스패닝 트리는 여러개일 수도 있다.

또한 MST도 여러개일 수 있지만, 스패닝 트리 개수 이하이다.

MST를 구하는 알고리즘은 프림알고리즘, 크루스칼 알고리즘 등이 있지만,

크루스칼 알고리즘이 응용 가능성이 높다.

크루스칼 알고리즘의 작동 방식

1. 간선들을 가중치 순으로 오름차순 정렬하고, 정점들을 각 컴포넌트로 초기화한다.

2. 간선들을 훑으면서 양쪽 정점을 포함한 컴포넌트가 연결되어 있지 않으면 간선을 뽑고 연결한다.

3. 간선 N-1개가 뽑혔을 때, 그 간선들과 정점들이 이루는 그래프가 MST이다.

크루스칼 알고리즘은 MST에 포함되어야 하는 간선을 처음부터 하나씩 골라내는 방식이다.

처음 상태는 정점만 있고 간선이 없는 상태이며

목표 상태는 모든 정점들이 하나의 연결된 성분에 포함되어야 한다.

가장 작은 가중치의 간선부터 차례대로 포함시킬지 말지를 선택해 나간다.

간선 추가시 Cycle이 생긴다면,

지금까지 사용한 간선보다 현재 추가하려는 간선의 가중치가 더 크다는 것이고,

또한 이말은 추가하려는 간선 양쪽의 정점이 이미 같은 연결된 성분에 포함되어 있다는 의미이므로

MST에 포함시키지 않는다.

양쪽 끝 정점이 같은 컴포넌트, 즉 같은 연결된 성분에 속해있는지 아닌지를 빠르게 확인하기 위해

유니온 파인드 기법을 사용한다.

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
 
 
// 백준/MST/크루스칼 : https://www.acmicpc.net/problem/1922
public class ba1922_kruskal_mst {
    static int N, M, result;
    static ArrayList<Edge1922> edge;
    static int par[];
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer  st;
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());
 
        edge = new ArrayList<>();
 
        for(int i=1; i<=M; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            edge.add(new Edge1922(a, b, c));
        }
        Collections.sort(edge);
        par = new int[N+1];
        for(int i=1; i<=N; i++){
            par[i] = i;
        }
 
        for(Edge1922 e : edge){
            int se = e.start;
            int ee = e.end;
            int ec = e.cost;
            if(find(se) != find(ee)){
                union(se, ee);
                result += ec;
            }
        }
        System.out.println(result);
    }
    private static int find(int a){
        if(par[a] == a) return a;
        par[a] = find(par[a]);
        return par[a];
    }
    private static void union(int a, int b){
        if(find(a) != find(b)) {
            par[find(a)] = find(b);
        }else{
            return;
        }
    }
}
class Edge1922 implements Comparable<Edge1922>{
    int start, end, cost;
    public Edge1922(int start, int end, int cost){
        this.start = start;
        this.end = end;
        this.cost = cost;
    }
 
    @Override
    public int compareTo(Edge1922 o) {
        if(this.cost < o.cost){
            return -1;
        }else if(this.cost > o.cost){
            return 1;
        }else{
            return 0;
        }
    }
}