크루스칼(Kruskal) 알고리즘의 구현 (JAVA)

 

이번 포스팅에서는 최소신장트리를 찾는알고리즘중 간선을 중심으로 생각해 최소신장트리를 구하는

알고리즘인 크루스칼 알고리즘을 다뤄보도록하겠다.

 

먼저 크루스칼 알고리즘에 앞서 최소 신장 트리의 개념부터 정의하고 넘어가도록 하겠다.

 

최소 신장 트리란?

 

먼저 트리는 그래프의 일종으로 순환하지 않는 형태의 그래프를 트리라고 한다.

이때 신장트리 즉 Spanning Tree는 이런 트리의 형태중 최소의 연결만을 갖는 트리를 신장트리라고 한다.

즉 N개의 정점을 갖는 그래프가 있다면 최소의 연결만을 갖도록 하려면 간선의 수는 N - 1개를 갖는 그래프가 될것이고 이를 신장 트리라고 한다.

 

이런 하나의 그래프에서 이런 신장트리는 여러개가 나올수 있는데 그중에서 간선의 비용을 최소로 갖는 경우를 최소 신장 트리 (Minimun Spanning Tree) 라고 한다.

 

 

예시를 들자면 

 

다음과 같은 그래프가 있다고 가정하면,

 

 

 

나올수 있는 신장트리는 여러가지가 있지만 몇가지를 추리면 다음과 같은 형태의 신장트리가 있을것이다.

 

 

 

 

정점의 개수가 6개 이므로 간선의 수가 5인 트리를 찾으면 되므로 더 많은 신장트리를 찾을수 있을것이다.

 

그러나 최소비용을 갖는 최소 신장 트리는 간선의 비용이 최소가 되는 경우이므로 다음과 같은 형태의

트리가 최소 신장 트리가 될것이다.

 

현재 그래프의 최소 신장 트리

 

 

 

 

---

 

 

그럼 이제 본론으로 넘어가서 최소신장트리를 구하는 알고리즘인 크루스칼 알고리즘은 어떤 방식으로 

최소 신장 트리를 찾는가를 알아보도록 하겠다.

 

크루스칼 알고리즘

 

크루스칼 알고리즘은 다음의 단계에 따라 진행되며 최소비용을 같는 신장트리를 찾는다.

 

0. 먼저 모든 정점이 연결되어 있지 않다고 가정하고 모든 간선정보만을 기준으로 생각한다.

1. 간선들을 비용을 기준으로 오름차순으로 정렬한다.

2. 정렬된 간선을 하나씩 가져온다.

3. 순환하지 않는 간선인 경우 간선의 정보를 저장하고, 연결한다.

4. 정렬된 모든 간선을 순회하며 2,3을 반복한다.

 

연결한다 라는 문장에서 알수 있듯이 크루스칼 알고리즘은 지난 포스팅에서 다뤘던 Union-Find 알고리즘을

응용하는 알고리즘이다. 즉 현재 정점의 연결 정보를 가져오거나, 연결할때 Union-Find를 활용하면 될것이다.

 

Union-Find에 대해 알고싶다면 하단의 링크를 참조하도록 하자.

 

https://0bliviat3.tistory.com/75

Union-Find 알고리즘의 구현 (JAVA)

 

 

그럼 위에서 예시로 들었던 그래프를 다시 가져와 단계적으로 알고리즘의 진행을 살펴보도록 하겠다.

 

 

먼저 이 그래프는 6개의 정점, 9개의 간선정보를 갖는 그래프이다.

그리고 크루스칼 알고리즘은 간선을 기준으로 생각하는 알고리즘이므로 간선의 정보를

다음과 같은 형태로 저장하도록 하겠다.

 

 

그리고 간선의 비용을 기준으로 오름차순으로 정렬한다면 다음과 같이될것이다.

 

 

 

이제 순서대로 간선 정보를 살펴보면서 연결할지를 결정하면 된다.

 

기존 그래프에서 연결된 선은 빨간선으로 표시하고 현재 살펴보는 간선은 초록색으로 표시하며 보도록하겠다. 먼저 볼 간선은 4와 6을 연결하고 있는 비용 5인 간선이다.

 

 

처음엔 연결한 간선이 없으므로 현재 간선을 저장하고, 연결후 다음 간선으로 진행한다.

 

 

현재 보고 있는 간선을 연결한다고 해도 순환하지 않기 때문에 저장하고 ,연결후 다음 간선으로 진행한다.

 

 

5번 정점과 4번 정점을 연결하는 비용 12 간선도 마찬가지다.

 

 

 

 

이번 간선은 1번 정점과 6번 정점을 연결하는 간선으로 연결하는 순간,

순환하며 트리가 아니게 되므로 무시하고 다음 간선으로 진행한다.

 

 

 

다음 간선 역시 연결하면 순환하게 되므로 무시하고 다음 간선으로 진행한다.

 

 

 

1번 정점과 2번 정점을 연결해도 순환하지 않으므로 저장후 연결한다.

 

이후의 단계는 설명을 생략하고 그림으로만 진행하도록 하겠다.

 

 

 

최소 신장 트리

 

 

이와 같은 과정을 통해 간선의 정보를 통해 최소 신장 트리를 구할수 있게 되었고

해당 비용은 5 + 10 + 12 + 20 + 30 = 77 임을 알 수 있다.

 

그럼 이를 코드로 구현 해보도록 하겠다.

 

 

---

 

 

구현

 

먼저 간선의 정보를 저장할 클래스를 하나 정의하도록 하겠다.

 

간선의 정보는 연결할 정점 두개와 간선의 비용을 필드로 갖는다.

 

class Node {
    int start;
    int end;
    int cost;

    Node(int start, int end, int cost) {
        this.start = start;
        this.end = end;
        this.cost = cost;
    }
}

 

그리고 정렬시 간선의 비용을 기준으로 정렬할 수 있도록 재정의 해준다.

 

class Node implements Comparable<Node>{
    int start;
    int end;
    int cost;

    Node(int start, int end, int cost) {
        this.start = start;
        this.end = end;
        this.cost = cost;
    }

    @Override
    public int compareTo(Node o) {
        return this.cost - o.cost;
    }
}

 

 

그리고 모든 간선정보를 저장후 정렬한뒤 Union-Find 알고리즘을 사용해 연결관계를 찾고 연결하고를

반복하며 모든 간선을 순회하면 된다.

 

    private int kruskal() {
        int minSum = 0;
        Collections.sort(edges);
        for(Node node : edges) {
            if(!find(node.start, node.end)) {
                minSum += node.cost;
                union(node.start, node.end);
            }
        }
        return minSum;
    }

 

 

이제 위의 그래프의 간선정보를 데이터로 넣어 확인해본다면 다음과 같은 결과를 얻을 수 있다.

 

이는 위에서 설명하며 얻은 최소비용과 동일함을 알 수 있다.

 

아래는 소스의 전문이다.

 

package impl;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class SpanningTree {

    private List<Node> edges;
    private List<Integer> parent;

    private void clear(int n) {
        edges = new ArrayList<>();
        parent = new ArrayList<>();
        for(int i = 0; i <= n; i++) {
            parent.add(i);
        }
    }

    private int getParent(int x) {
        if(parent.get(x) == x) {
            return x;
        }
        parent.set(x, getParent(parent.get(x)));
        return parent.get(x);
    }

    private boolean find(int a, int b) {
        return getParent(a) == getParent(b);
    }

    private void union(int a, int b) {
        a = getParent(a);
        b = getParent(b);
        if(a != b) {
            parent.set(b, a);
        }
    }

    private int kruskal() {
        int minSum = 0;
        Collections.sort(edges);
        for(Node node : edges) {
            if(!find(node.start, node.end)) {
                minSum += node.cost;
                union(node.start, node.end);
            }
        }
        return minSum;
    }

    private void init() {
        edges.add(new Node(4, 6, 5));
        edges.add(new Node(1, 5, 10));
        edges.add(new Node(1, 6, 15));
        edges.add(new Node(4, 5, 12));
        edges.add(new Node(4, 3, 36));
        edges.add(new Node(2, 3, 30));
        edges.add(new Node(2, 5, 25));
        edges.add(new Node(1, 2, 20));
        edges.add(new Node(5, 6, 17));
    }

    void run() {
        clear(6);
        init();
        System.out.println(kruskal());
    }

    public static void main(String[] args) {
        SpanningTree MSTInstance = new SpanningTree();
        MSTInstance.run();
    }

    
}

class Node implements Comparable<Node>{
    int start;
    int end;
    int cost;

    Node(int start, int end, int cost) {
        this.start = start;
        this.end = end;
        this.cost = cost;
    }

    @Override
    public int compareTo(Node o) {
        return this.cost - o.cost;
    }
}