크루스칼 알고리즘

최준병·2025년 5월 18일

신장(伸張)

伸 : 펼 신
張 : 베풀 장

세력이나 권리 따위가 늘어남. 또는 늘어나게 함.

신장 트리(Spanning Tree)

그래프 상에서 모든 노드가 사이클 없이 연결된 무방향 그래프
다시 말해, 모든 노드에서 다른 모든 노드까지 도달할 수 있고 사이클이 발생하지 않는 그래프를 말한다.
모든 노드에서 다른 모든 노드까지 도달할수 있고 사이클이 발생하지 않는다는 조건은 트리의 성립조건이기도 해 신장 "트리" 라고 부른다.

최소 신장 트리(Minimum Spanning Tree, MST)

신장 트리 중 간선의 가중치 합이 가장 작은 트리를 말합니다.

크루스칼 알고리즘

최소 신장 트리를 찾는 알고리즘

핵심 원리

그리디 + 서로소 집합 자료구조를 이용해 구현할 수 있습니다.

그리디
가중치가 적은 간선을 먼저 연결하므로써 최소 비용으로 연결할 수 있습니다.
서로소 집합 자료구조
DSU를 이용해 사이클 탐지 를 하여 신장 트리를 구성할 수 있습니다.

동작 과정

간선 데이터를 가중치가 작은 순으로 정렬합니다.
“가중치가 작은 간선”을 먼저 선택해 정점들을 최소 비용으로 연결합니다.
서로소 집합 자료구조를 사용하여 사이클이 생기는지 확인합니다.
사이클이 생기지 않는다면 해당 간선을 최소 신장 트리에 포함시킵니다.
위 과정을 모든 간선에 대해 반복하거나, (정점 수 – 1)개의 간선을 골랐을 때 종료합니다.

구현 코드

import java.util.*;

class Edge implements Comparable<Edge> {

    private int distance;
    private int nodeA;
    private int nodeB;

    public Edge(int distance, int nodeA, int nodeB) {
        this.distance = distance;
        this.nodeA = nodeA;
        this.nodeB = nodeB;
    }

    public int getDistance() {
        return this.distance;
    }

    public int getNodeA() {
        return this.nodeA;
    }

    public int getNodeB() {
        return this.nodeB;
    }

    // 거리(비용)가 짧은 것이 높은 우선순위를 가지도록 설정
    @Override
    public int compareTo(Edge other) {
        if (this.distance < other.distance) {
            return -1;
        }
        return 1;
    }
}

public class Main {

    // 노드의 개수(V)와 간선(Union 연산)의 개수(E)
    // 노드의 개수는 최대 100,000개라고 가정
    public static int v, e;
    public static int[] parent = new int[100001]; // 부모 테이블 초기화하기
    // 모든 간선을 담을 리스트와, 최종 비용을 담을 변수
    public static ArrayList<Edge> edges = new ArrayList<>();
    public static int result = 0;

    // 특정 원소가 속한 집합을 찾기
    public static int findParent(int x) {
        // 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
        if (x == parent[x]) return x;
        return parent[x] = findParent(parent[x]);
    }

    // 두 원소가 속한 집합을 합치기    
	public static void union(int a, int b){
        int rootA = findParent(a);
        int rootB = findParent(b);

        if(rootA > rootB){
            parent[rootA] = rootB;
        }else{
            parent[rootB] = rootA;
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        v = sc.nextInt();
        e = sc.nextInt();

        // 부모 테이블상에서, 부모를 자기 자신으로 초기화
        for (int i = 1; i <= v; i++) {
            parent[i] = i;
        }

        // 모든 간선에 대한 정보를 입력 받기
        for (int i = 0; i < e; i++) {
            int a = sc.nextInt();
            int b = sc.nextInt();
            int cost = sc.nextInt();
            edges.add(new Edge(cost, a, b));
        }

        // 간선을 비용순으로 정렬
        Collections.sort(edges);

        // 간선을 하나씩 확인하며
        for (int i = 0; i < edges.size(); i++) {
            int cost = edges.get(i).getDistance();
            int a = edges.get(i).getNodeA();
            int b = edges.get(i).getNodeB();
            // 사이클이 발생하지 않는 경우에만 집합에 포함
            if (findParent(a) != findParent(b)) {
                union(a, b);
                result += cost;
            }
        }

        System.out.println(result);
    }
}