[최소 신장 트리] 크루스칼(Kruskal)

크루스칼 알고리즘

가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘

동작 과정

1. 간선 정보를 오름차순으로 정렬
2. 비용이 적은 간선부터 차례로 그래프에 포함
   • 사이클을 형성하는 경우 간선을 포함하지 않음

코드

import java.io.*;
import java.util.*;

public class Kruskal {
    static int[] parents;

    static int find(int x) {
        if(parents[x] != x) parents[x] = find(parents[x]);
        return parents[x];
    }

    static void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);

        if (rootX != rootY) {
            parents[rootY] = rootX;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        ArrayList<Node> edges = new ArrayList<>();
        parents = new int[N + 1];

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());

            edges.add(new Node(u, v, w));
        }

        Collections.sort(edges);

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

        int result = 0;
        for(Node edge: edges) {
            if (find(edge.u) != find(edge.v)) {
                union(edge.u, edge.v);
                result += edge.w;
            }
        }
    }

    static class Node implements Comparable<Node> {
        int u, v, w;

        public Node(int u, int v, int w) {
            this.u = u;
            this.v = v;
            this.w = w;
        }

        @Override
        public int compareTo(Node o) {
            return Integer.compare(this.w, o.w);
        }
    }
}