[Greedy] 그리디 알고리즘 - 크루스칼 알고리즘

≣ 목차

 

크루스칼 알고리즘

그래프에서 가장 적은 비용으로 모든 노드를 연결하면서 전체 간선 가중치의 합이 최소가 되는 알고리즘입니다. 다시 말해 최소 신장 트리(MST)를 만들기 위한 대표적인 알고리즘이라고 할 수 있습니다. 예를 들어, 여러 개의 도시가 있을 때 각 도시를 도로를 이용해 연결하고자 할 때 비용을 최소한으로 하고자 할 때 실제로 적용되는 알고리즘입니다. 추가적으로 전체 노드를 연결할 때 간선의 갯수는 전체 노드 갯수 -1이 간선의 갯수가 됩니다.

 

용어 정리

노드 = 정점 = 목표: 그래프에서 동그라미 부분

간선 = 거리 = 비용: 그래프에서 선에 해당하는 부분

가중치: 각 간선이 가지는 값으로, 일반적으로 두 노드 간의 거리, 비용, 또는 시간을 의미합니다.

 

위에 내용을 토대로 아래 그래프를 살펴보았을 때 노드의 갯수는 4개, 간선의 갯수는 5개 입니다.

크루스칼 알고리즘의 핵심 개념은 가중치가 작은 간선을 순서대로 연결하면 됩니다. 단! 사이클이 생기면 안됩니다.

 

왜 사이클이 생기면 안될까요??

왜냐하면 불필요한 간선으로 인해 비용이 증가하는 문제는 이미 연결된 노드끼리 다시 연결할 경우 발생합니다. 이러한 중복 연결은 쓸데없는 비용만 추가하게 되어 최소 비용을 구하려는 목적과 어긋나게 됩니다. 같은 집합에 속하는 노드들을 다시 연결하려고 할 때, Union-Find 알고리즘을 통해 확인하면 이미 같은 집합에 속해 있다는 사실을 알 수 있습니다. 이 상태에서 추가로 간선을 연결하면 순환(cycle)이 생기게 되며, 이는 그래프의 구조를 비효율적으로 변하게 하고, 최적화된 경로를 찾는 데 방해가 되므로 사이클이 생기는 것을 피해야 합니다.

 

 

크루스칼 알고리즘 적용 순서

1. 크루스칼 알고리즘은 최대한 적은 비용으로 연결만 하면 되기 때문에 가중치를 기준으로 오름 차순으로 정렬합니다.

출발 노드	도착 노드	가중치
1	2	2
1	3	4
2	3	5
2	4	7
3	4	10

 

2. 이제 가중치가 작은 간선을 연결하면 됩니다.

2-1. (1, 2) 연결

2-2. (1, 3) 연결

2-3. (2, 3) 연결을 하면 사이클이 생기기 때문에 해당 간선은 연결하지 않습니다.

 

2-4 (2, 4) 연결을 하지 노드가 모두 연결되었기 때문에 더 이상 간선은 필요하지 않습니다.

크루스칼 알고리즘의 적용 순서는 먼저 간선을 가중치 기준으로 오름차순 정렬한 다음, 가장 짧은 간선부터 하나씩 선택하면서 사이클이 생기지 않도록 연결하는 과정을 반복합니다. 이때, 선택한 간선이 연결된 두 노드가 이미 같은 집합에 속해 있는지를 확인하여 사이클을 방지하며, 모든 노드가 하나의 트리가 될 때까지 이 과정을 계속 진행합니다.

 

크루스칼 알고리즘에 시간 복잡도

크루스칼 알고리즘은 최소 신장 트리를 찾기 위한 효율적인 방법으로, 주로 세 가지 주요 단계로 구성됩니다. 간선 정렬, 간선 순회, 그리고 서로소 집합 연산입니다.

 

먼저, 간선 정렬 단계에서는 모든 간선을 가중치에 따라 오름차순으로 정렬하는데, 이 과정의 시간 복잡도는 O(ElogE)입니다. 다음으로, 간선 순회 단계에서는 정렬된 간선을 하나씩 확인하며, 이를 통해 사이클이 발생하지 않는 경우에만 간선을 선택합니다. 이 단계는 간선의 개수에 비례하여 O(E)의 시간이 소요됩니다. 마지막으로, 서로소 집합 연산은 두 정점이 같은 집합에 속하는지를 확인하고, 필요에 따라 집합을 합치는 작업으로, 일반적으로 O(1)의 시간 복잡도를 가집니다. 크루스칼 알고리즘에서 간선을 정렬하는데 걸리는 시간이 매우 많기 때문에 시간 복잡도는 O(ElogE)입니다.

종류	정렬	간선 순회	서로수 집합 연산
시간 복잡도	O(ElogE)	O(E)	O(1)

 

 

예제 문제 : 도시들을 도로로 연결하기

문제 설명

• N개의 도시가 있고, 도시들을 연결하는 M개의 도로가 있습니다.
• 각 도로는 두 도시를 연결하며 건설 비용이 주어집니다.
• 모든 도시를 서로 연결하되, 총 비용이 최소가 되도록 도로를 선택

import java.util.*;

public class Example {
    static class Test implements Comparable<Test> {
        int from, to, weight; // 시작 노드, 종료 노드, 가중치

        public Test(int from, int to, int weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }

        // compareTo을 이용해 오름차순으로 정렬
        @Override
        public int compareTo(Test o) {
            return this.weight - o.weight;
        }
    }

    static int[] parent;

    // 루트 노드를 찾는 함수
    public static int find(int x) {
        if (parent[x] == x) return x;
        return parent[x] = find(parent[x]);
    }

    // 두 노드를 같은 집합으로 묶는 함수
    public static void union(int a, int b) {
        a = find(a);
        b = find(b);
        if (a != b) parent[b] = a;
    }

    public static void main(String[] args) {
        int n = 4; // 노드 갯수
        List<Test> list = new ArrayList<>();
        list.add(new Test(1, 2, 13));
        list.add(new Test(1, 3, 22));
        list.add(new Test(3, 2, 31));
        list.add(new Test(2, 4, 44));
        list.add(new Test(3, 4, 55));

        // 초기 부모 설정 (자기 자신이 부모)
        parent = new int[n + 1];
        for (int i = 1; i <= n; i++) {
            parent[i] = i;
        }

        // 가중치 오름차순으로 정렬
        Collections.sort(list);

        int totalCost = 0;

        for (Test temp : list) {
            // 사이클 여부 검사
            if (find(temp.from) != find(temp.to)) {
                union(temp.from, temp.to);
                totalCost += temp.weight;
                System.out.println("간선 루트: " + temp.from + " > " + temp.to + " \n비용: " + temp.weight);
            }
        }

        System.out.println("총 최소 비용: " + totalCost);
    }
}

 

 

 

참고자료

https://velog.io/@sy508011/%EA%B7%B8%EB%9E%98%ED%94%84-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%ED%81%AC%EB%A3%A8%EC%8A%A4%EC%B9%BC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Kruskal-Algorithm#%ED%81%AC%EB%A3%A8%EC%8A%A4%EC%B9%BC-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-kruskal-algorithm

[그래프 알고리즘] 크루스칼 알고리즘 Kruskal Algorithm