Kruskal Algorithm 이란?

Kruskal Algorithm(크루스칼 알고리즘)은 최소 신장 트리(Minimum Spanning Tree)를 찾는 알고리즘이다. 가중치가 가장 작은 선분이 사이클을 만들지 않을때만 선분을 추가 시켜 최소 신장 트리를 찾는다.

Kruskal Algorithm은 간선을 가중치 순으로 오름차순 정렬한 후, 가중치가 작은 간선부터 하나씩 선택해 최소 신장 트리를 만든다. 만약 선택한 간선이 사이클을 형성하면 간선을 선택하지 않고 다음으로 작은 간선을 선택한다.

Kruskal Algorith의 시간 복잡도는 간선의 개수를 E, 정점의 개수를 V 라고 할 때, 간선을 정렬 하는데 가장 빠른 정렬 알고리즘의 시간 복잡도는 O(nlogn)이기 때문에 O(ElogE)의 시간이 든다. 그리고 각각의 간선에 대해 Union-Find 연산을 수행하는데 O(logV)의 시간이 걸리기 때문에 Kruskal Algorithm의 시간 복잡도는 O(ElogE)이다.

Kruskal Algorithm 과정

1. 그래프에서 간선들을 가중치 순으로 오름차순으로 정렬합니다.
2. 정렬된 간선들 중 가장 작은 가중치를 갖는 간선을 선택합니다.
3. 선택한 간선의 두 끝 정점이 같은 집합에 속해있다면, 해당 간선을 선택하지 않습니다. 다음으로 작은 가중치를 갖는 간선을 선택합니다.
4. 선택한 간선의 두 끝 정점이 다른 집합에 속해있다면, 해당 간선을 선택하고, 두 끝 정점이 속한 집합을 합칩니다. 이를 Union-Find 알고리즘을 이용해 구현할 수 있습니다.
5. 모든 정점이 포함되어 있을 때까지 2~4번 과정을 반복합니다.

Kruskal Pseudo-code

입력 : 가중치 그래프 G = (V, E) , |V| = n(점의 수), |E| = m(간선의 수)

출력 : 최소 신장 트리 T

1. 가중치의 오름차순으로 간선들을 정렬한다. 정렬된 간선리스트를 L이라 한다

2. T = Ø  // 트리 T를 초기화 시킨다

3. while(T의 간선수 < n - 1){
    L에서 가장 작은 가중치 간선 e, e를 L에서 제거
    if(e가 T에 추가, 사이클을 만들지 않는다면)
        e를 T에 추가한다
    else    //사이클이 생기는 경우
        e를 버린다
}

4. return 트리 T

Kruskal 출처:https://upload.wikimedia.org/wikipedia/commons/thumb/b/bb/KruskalDemo.gif/220px-KruskalDemo.gif

Kruskal Algorithm 구현

import java.util.*;

public class main {

    public static void main(String[] args) {

        // 그래프의 간선 정보를 초기화합니다.
        Edge[] edges = {
                new Edge('a', 'b', 8),
                new Edge('a', 'd', 2),
                new Edge('a', 'e', 4),
                new Edge('b', 'c', 1),
                new Edge('b', 'd', 4),
                new Edge('b', 'f', 2),
                new Edge('c', 'f', 1),
                new Edge('d', 'e', 3),
                new Edge('d', 'f', 7),
                new Edge('e', 'f', 9)
        };

        // 간선의 가중치를 기준으로 오름차순으로 정렬합니다.
        Arrays.sort(edges);

        // 각 정점의 부모를 저장할 배열을 초기화합니다.
        Map<Character, Character> parent = new HashMap<>();
        for (Edge edge : edges) {
            parent.put(edge.start, edge.start);
            parent.put(edge.end, edge.end);
        }

        // 최소 신장 트리를 구성할 간선을 저장할 리스트를 초기화합니다.
        List<Edge> mst = new ArrayList<>();

        // 간선을 하나씩 검사하며 최소 신장 트리를 구성합니다.
        for (Edge edge : edges) {
            char startParent = find(parent, edge.start);
            char endParent = find(parent, edge.end);

            // 시작 정점과 끝 정점의 부모가 같으면 사이클이 형성되므로 건너뜁니다.
            if (startParent == endParent) {
                continue;
            }

            // 두 정점의 부모가 다르면 간선을 추가하고 두 정점을 연결합니다.
            mst.add(edge);
            union(parent, startParent, endParent);
        }

        // 최소 신장 트리를 출력합니다.
        System.out.println("Minimum Spanning Tree:");
        for (Edge edge : mst) {
            System.out.println(edge.start + " - " + edge.end + " : " + edge.weight);
        }
    }

    // 정점의 부모를 찾는 메소드입니다.
    private static char find(Map<Character, Character> parent, char vertex) {
        if (parent.get(vertex) == vertex) {
            return vertex;
        }
        return find(parent, parent.get(vertex));
    }

    // 두 정점을 연결하는 메소드입니다.
    private static void union(Map<Character, Character> parent, char vertex1, char vertex2) {
        char parent1 = find(parent, vertex1);
        char parent2 = find(parent, vertex2);
        if (parent1 != parent2) {
            parent.put(parent1, parent2);
        }
    }
}

class Edge implements Comparable<Edge> {
    char start;
    char end;
    int weight;

    public Edge(char start, char end, int weight) {
        this.start = start;
        this.end = end;
        this.weight = weight;
    }

    @Override
    public int compareTo(Edge other) {
        return Integer.compare(this.weight, other.weight);
    }
}

실행 결과

Minimum Spanning Tree:
b - c : 1
c - f : 1
a - d : 2
d - e : 3
b - d : 4