크루스칼 알고리즘 : 최소 신장 트리(MST)를 찾는 알고리즘

신장 트리란 그래프에서 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프를 의미한다. 모든 노드가 포함되어 서로 연결되면서 사이클이 존재하지 않는다는 조건은 트리의 조건이기도 하다.

최소 신장 트리(MST)

최소한의 비용으로 구성되는 신장 트리를 찾아야 하는 경우 → 예를 들어 N개의 도시가 있을 때, 두 도시 사이에 도로를 놓아 전체 도시가 서로 연결되도록 최소한의 비용으로 도로를 설치하는 경우

크루스칼 알고리즘

크루스칼 알고리즘은 대표적인 최소 신장 트리 알고리즘으로 간선을 중심으로 해결한다. 그리디 알고리즘으로 분류된다.

동작과정

1. 간선 데이터를 비용에 따라 오름차순 정렬
2. 간선을 하나씩 확인하며 현재의 간선이 사이클을 발생시키는지 확인
    2-1. 사이클이 발생하지 않는 경우 최소 신장 트리에 포함
    2-2. 사이클이 발생하는 경우 최소 신장 트리에 포함X
3. 모든 간선에 대해 2번 과정 반복

 

오름차순 정렬 후, 처리하지 않은 간선 중에서 가장 짧은 간선인 (3, 4) 선택하여 처리

간선을 하나씩 확인하며 사이클 발생 여부에 따라 최소 신장 트리에 포함할지 포함하지 않을지 결정한다. 최소 신장 트리에 포함되어 있는 간선의 비용을 모두 더하면, 그 값이 최종 비용에 해당한다.

 

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

public class Main {

    static class Edge implements Comparable<Edge> {
        int distance;
        int nodeA;
        int nodeB;

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

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

    static int v, e;
    static int[] parent = new int[100001];
    static ArrayList<Edge> edges = new ArrayList<>();
    static int result = 0;
    // 특정 원소가 속한 집합 찾기
    public static int findParent(int x) {
        // 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적 호출
        if (x == parent[x])
            return x;
        return findParent(parent[x]);
    }

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

        if (a < b) parent[b] = a;
        else parent[a] = b;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

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

        boolean cycle = false;

        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).distance;
            int a = edges.get(i).nodeA;
            int b= edges.get(i).nodeB;
            
            if(findParent(a) != findParent(b)) {
                unionParent(a, b);
                result += cost;
            }
        }

        System.out.println(result);
    }
}

 

유니온파인드 알고리즘은 시간복잡도가 상수이므로 간선들을 정렬하는 데 시간이 걸린다. 따라서 O(ElogE)의 시간복잡도를 가진다.