신장 트리

• 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미합니다.
  (모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 조건과 같습니다.)

최소 신장 트리

• 최소한의 비용으로 구성되는 신장 트리를 찾는 알고리즘

크루스칼 알고리즘

• 대표적인 최소 신장 트리 알고리즘
• 그리디 알고리즘으로 분류

동작 과정

1. 간선 데이터를 비용을 따라 오름차순으로 정렬
2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인 (이때, 사이클 발생 여부는 유니온파인드를 사용해 판별)
   1 – 사이클이 발생하지 않는 경우 최소 신장 트리에 포함
   2 – 사이클이 발생하는 경우 최소 신장 트리에 포함시키지 않음
3. 모든 간선에 대해 2번의 과정을 반복

예시

백준 1197번 최소 스패닝 트리

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

public class BaekJoon1197 {
    static int[] parent;
    static PriorityQueue<pEdge> queue = new PriorityQueue<>();

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int V = Integer.parseInt(st.nextToken());
        int E = Integer.parseInt(st.nextToken());

        parent = new int[V + 1];

        for (int i = 1; i <= V; i++) {
            parent[i] = i;
        }

        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            queue.add(new pEdge(s, e, v));
        }

        int useEdge = 0;
        int ans = 0;

        while (useEdge < V - 1) {
            pEdge cur = queue.poll();

            if (find(cur.s) != find(cur.e)) {
                ans += cur.v;
                useEdge++;
                union(cur.s, cur.e);
            }
        }

        System.out.println(ans);

    }

	// 유니온 파인드
    private static int find(int num) {
        if (parent[num] == num) {
            return num;
        } else {
            return parent[num] = find(parent[num]);
        }
    }

    private static void union(int num1, int num2) {
        int a = find(num1);
        int b = find(num2);

        if (a != b) {
            parent[b] = a;
        }
    }

    static class pEdge implements Comparable<pEdge> {
        int s;
        int e;
        int v;

        pEdge(int s, int e, int v) {
            this.s = s;
            this.e = e;
            this.v = v;
        }
		
        // 비용 기준 오름차순 정렬
        @Override
        public int compareTo(pEdge o) {
            return this.v - o.v;
        }
    }
}