[알고리즘] 크루스칼(Kruskal) 알고리즘

크루스칼(Kruskal) 알고리즘

이 알고리즘은 가장 적은 비용으로 모든 노드를 연결하기 위해 사용하는 알고리즘이다. 사이클(Cycle)을 만들지 않는 범위에서 최소 비용 간선(Edge)을 하나씩 더해가며 최소 신장 트리(Minimum Spanning Tree, MST)를 만든다. 실제로 여러 도시가 있을 때 각 도시를 도로로 연결하는데 최소 비용을 들여 연결할 때 사용될 수 있는 알고리즘이다.

 

<간선을 거리가 짧은 순서대로 그래프에 포함하는데, Cycle이 형성되면 안된다.>

 

 n개의 정점으로 트리를 만드는데 n-1개의 간선이 필요하므로, 처음에 간선이 없는 상태에서 시작하여 n-1개의 간선을 더하는 것이다. 크루스칼 알고리즘은 프림 알고리즘 처럼 하나의 트리를 키워나가는 방식이 아니고, 임의의 시점에 최소 비용의 간선을 더하므로 여러 개의 트리가 산재하게 된다.

 크루스칼은 시작점을 정하지 않고 최소 비용의 간선을 차례로 대입하며 최소 신장 트리를 구성하므로, 그 과정에서 Cycle이 생성되는지 확인하여야 한다. Cycle을 확인하는 방법으로는 Union-Find가 있다.

크루스칼 알고리즘 과정

1. 모든 간선을 끊어 놓는다.
2. 가중치(Weight) 순으로 간선들을 오름차순 정렬한다.
3. 정렬된 간선을 순서대로 선택한다.
4. 선택한 두 간선의 정점이 연결되어있지 않으면, 해당 간선을 MST에 포함시키고 두 정점을 연결한다.

1) 가장 작은 가중치 10을 갖는 간선은 정점 0과 5를 잇는다. 정점 0과 5는 연결되어있지 않으므로 연결하고 MST에 포함한다.

 

2) 그 다음 가장 작은 가중치 12를 갖는 간선은 정점 2와 3을 잇는다. 정점 2와 3은 연결되어있지 않으므로 연결하고 MST에 포함한다.

3) 그 다음 가장 작은 가중치 15를 갖는 간선은 정점 1과 6을 잇는다. 정점 1과 6은 연결되어있지 않으므로 연결하고 MST에 포함한다.

 

4) 그 다음 가장 작은 가중치 16을 갖는 간선은 정점 1과 2를 잇는다. 정점 1과 2는 연결되어있지 않으므로 연결하고 MST에 포함한다.

5) 그 다음 가장 작은 가중치 18을 갖는 간선은 정점 3과 6을 잇는다. 정점 3과 6은 서로 연결되어있으므로 연결하지 않는다.

 

6) 그 다음 가장 작은 가중치 22를 갖는 간선은 정점 3과 4를 잇는다. 정점 3과 4는 연결되어있지 않으므로 연결하고 MST에 포함한다.

7) 그 다음 가장 작은 가중치 25를 갖는 간선은 정점 4와 6을 잇는다. 정점 4와 6은 연결되어 있으므로 연결하지 않는다.

 

8) 그 다음 가장 작은 가중치 27을 갖는 간선은 정점 4와 5를 잇는다. 정점 4와 5는 연결되어있지 않으므로 연결하고 MST에 포함한다.

 

9) 마지막 간선은 가중치 29를 갖고 정점 0과 1을 잇는다. 정점 0과 1은 연결되어 있으므로 MST에 포함하지 않는다.

 

그림 출처 : goodgid님의 Github

최소 신장 트리의 비용 = 102

크루스칼 알고리즘의 수행 시간

크루스칼 알고리즘의 시간 복잡도는 정렬 알고리즘과 Union-Find 알고리즘의 합이라고 할 수 있으므로 정렬의 시간 복잡도와 동일하다고 판단해도 큰 무리가 없다고 한다.

 

조금 더 따져보자면,

모든 간선을 정렬하는데 O(Elog E) = O(Elog V)

최대 O(E)번의 Union-Find, V번의 Make-Set

 

모두 합치면 O((V+E)log*V)가 되는데 log*V는 거의 상수로 간주할 수 있으므로 결국 크루스칼 알고리즘의 시간을 좌우하는 것은 정렬 시간이다. 따라서 총 수행 시간은 O(Elog V)가 된다.

---

그럼 이제 간단하게 위의 그래프를 가지고 크루스칼 알고리즘을 이용하여 최소 신장 트리를 만드는 Java 코드를 짜보도록 하자.

 

# Edge class

    //간선의 정보를 갖는 클래스를 준비한다.
    static class Edge{
        int[] v = new int[2];
        int weight;

        public Edge(int v1, int v2, int weight){
            this.v[0] = v1; //정점
            this.v[1] = v2; //정점
            this.weight = weight; //가중치
        }

        @Override
        public String toString() {
            return "Edge{" +
                    "v=" + Arrays.toString(v) +
                    ", weight=" + weight +
                    '}';
        }
    }

# Union-Find

    /*Union-Find 메서드를 준비한다.*/
    //부모 노드를 찾는 함수
    static int getParent(int parent[], int x){
        if(parent[x] == x) return x;
        return parent[x] = getParent(parent, parent[x]);
    }
    //두 부모 노드를 합치는 함수
    static void unionParent(int parent[], int a, int b){
        a = getParent(parent, a);
        b = getParent(parent, b);

        if(a < b) parent[b] = a;
        else parent[a] = b;
    }
    //같은 부모를 가지는지 확인
    static boolean findParent(int[] parent, int a, int b){
        a = getParent(parent, a);
        b = getParent(parent, b);

        return (a==b)?true:false;
    }

# main

    public static void main(String[] args) {
        //간선 인스턴스 생성
        Edge[] edges = new Edge[9];
        edges[0] = new Edge(0, 1, 29);
        edges[1] = new Edge(1, 6, 15);
        edges[2] = new Edge(1, 2, 16);
        edges[3] = new Edge(2, 3, 12);
        edges[4] = new Edge(3, 4, 22);
        edges[5] = new Edge(4, 5, 27);
        edges[6] = new Edge(4, 6, 25);
        edges[7] = new Edge(3, 6, 18);
        edges[8] = new Edge(0, 5, 10);

        //union Array 초기화(각 정점은 자기 자신의 값을 가짐)
        for(int i=0; i<union.length; i++)
            union[i] = i;

        //List에 담아서 정렬
        EdgeComparator comparator = new EdgeComparator();
        List<Edge> list = Arrays.stream(edges).collect(Collectors.toList());
        list.sort(comparator);

        list.stream().forEach(System.out::println);

        int sum = 0;
        for(int i=0; i<list.size(); i++){

            Edge edge = list.get(i);

            //Cycle이 발생하지 않는 경우 Graph에 포함
            if(!findParent(union, edge.v[0], edge.v[1])) {
                sum += edge.weight;
                unionParent(union, edge.v[0], edge.v[1]);
            }
        }

        System.out.println("최소 신장 트리의 Cost : " + sum);
    }

Console 출력을 보면 간선들이 가중치를 기준으로 오름차순 정렬된 것을 볼 수 있고, 최소 신장 트리의 비용 또한 일치함을 알 수 있다.

# Code </>

public class KruskalExp {

    //간선의 정보를 갖는 클래스를 준비한다.
    static class Edge{
        int[] v = new int[2];
        int weight;

        public Edge(int v1, int v2, int weight){
            this.v[0] = v1;
            this.v[1] = v2;
            this.weight = weight;
        }

        @Override
        public String toString() {
            return "Edge{" +
                    "v=" + Arrays.toString(v) +
                    ", weight=" + weight +
                    '}';
        }
    }

    //Union Array를 준비한다.
    static int[] union = new int[7];

    /*Union-Find 메서드를 준비한다.*/
    //부모 노드를 찾는 함수
    static int getParent(int parent[], int x){
        if(parent[x] == x) return x;
        return parent[x] = getParent(parent, parent[x]);
    }
    //두 부모 노드를 합치는 함수
    static void unionParent(int parent[], int a, int b){
        a = getParent(parent, a);
        b = getParent(parent, b);

        if(a < b) parent[b] = a;
        else parent[a] = b;
    }
    //같은 부모를 가지는지 확인
    static boolean findParent(int[] parent, int a, int b){
        a = getParent(parent, a);
        b = getParent(parent, b);

        return (a==b)?true:false;
    }

    public static void main(String[] args) {
        //간선 인스턴스 생성
        Edge[] edges = new Edge[9];
        edges[0] = new Edge(0, 1, 29);
        edges[1] = new Edge(1, 6, 15);
        edges[2] = new Edge(1, 2, 16);
        edges[3] = new Edge(2, 3, 12);
        edges[4] = new Edge(3, 4, 22);
        edges[5] = new Edge(4, 5, 27);
        edges[6] = new Edge(4, 6, 25);
        edges[7] = new Edge(3, 6, 18);
        edges[8] = new Edge(0, 5, 10);

        //union Array 초기화(각 정점은 자기 자신의 값을 가짐)
        for(int i=0; i<union.length; i++)
            union[i] = i;

        //List에 담아서 정렬
        EdgeComparator comparator = new EdgeComparator();
        List<Edge> list = Arrays.stream(edges).collect(Collectors.toList());
        list.sort(comparator);

        list.stream().forEach(System.out::println);

        int sum = 0;
        for(int i=0; i<list.size(); i++){

            Edge edge = list.get(i);

            //Cycle이 발생하지 않는 경우 Graph에 포함
            if(!findParent(union, edge.v[0], edge.v[1])) {
                sum += edge.weight;
                unionParent(union, edge.v[0], edge.v[1]);
            }
        }

        System.out.println("최소 신장 트리의 Cost : " + sum);
    }
}

//정렬하기 위한 Comparator 인터페이스를 구현
class EdgeComparator implements Comparator<KruskalExp.Edge>{
    @Override
    public int compare(KruskalExp.Edge e1, KruskalExp.Edge e2) {

        int w1 = e1.weight;
        int w2 = e2.weight;

        //Order By ASC;
        if(w1 > w2)
            return 1;
        else if(w1 < w2)
            return -1;
        else
            return 0;
    }
}

# 복습 문제

1922번: 네트워크 연결

1197번: 최소 스패닝 트리

1647번: 도시 분할 계획

 # References  

미니님의 블로그

자바 객체로 구성된 리스트 정렬하기

goodgid님의 Github

크루스칼(Kruskal) 알고리즘

동빈나님의 블로그

18. 크루스칼 알고리즘(Kruskal Algorithm)