크루스칼 알고리즘

크루스칼 알고리즘의 다른 말로는 최소 신장 트리 알고리즘이라고 한다.

그러면 신장 트리는 무엇일까?

신장 트리는 하나의 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 그래프

사실 이건 트리의 성립 조건이라고 한다.

(내가 생각할 때 신장 트리는 몇 개의 선만 더 추가 되면 사이클이 되는게 일반적인 트리와 차이점인 것 같다.)

 

보통 크루스탈 알고리즘은 가능한 한 최소한의 비용으로 신장 트리를 찾아야 할 때가 있을때 사용이 된다고 한다.

이런식으로 각 노드를 방문하려면 23,25.13의 비용이 발생한다고 한다.

이들을 모두 방문하는 경우중 가장 작은 것이 무엇이냐라고 물어보는 것 과 최소 트리값을 찾는 것 은 같다.

즉, 23 + 13 이 된다 

위 그림은 3개중 하나가 제거 되야 크루스칼이 만족한다.

 

크루스칼 알고리즘은 다음과 같은 방법으로 동작한다고 한다.

1. 간선 데이터를 비용에 따라 오름차순으로 정렬한다.

2. 간선을 하나씩 확인 하면서 현재의 간선이 사이클을 발생 시키는지 확인한다.

    - 사이클이 발생시키지 않은 경우 최소 신장 트리에 포함시킨다.
    - 사이클이 발생하는 경우, 최소 트리에 포함시키지 않는다.

3. 모든 간선에 대해 2번의 과점을 반복한다.

즉, 1번 -> 2번 -> 3번 -> 2번 -> 2번 -> 2번 무한 반복 후 종료

이런식으로 되는 것 같다. 이제 코드로 확인해보자.

static class Node implements Comparable<Node>{
        int x;
        int y;
        int cost;

        public Node(int x, int y, int cost) {
            this.x = x;
            this.y = y;
            this.cost = cost;
        }

        @Override
        public int compareTo(Node o) {
            return this.cost - o.cost;
        }
    }
    static int findParent(int[] parent, int x) {

        if (parent[x] != x) {
            parent[x] = findParent(parent,parent[x]);
        }
        return parent[x];
    }

    static void unionParent(int[] parent, int a, int b) {
        a = findParent(parent,a);
        b = findParent(parent,b);

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

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

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

        int[] parent = new int[v+1];

        List<Node> edges = new ArrayList<>();
        int result = 0;

        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 Node(a,b,cost));
        }

        Collections.sort(edges);

        for(Node edge : edges) {
            int cost = edge.cost;
            int a = edge.x;
            int b = edge.y;

            if (findParent(parent,a) != findParent(parent,b)) {
                unionParent(parent,a,b);
                result += cost;
            }
        }

        System.out.println(result);
    }

 

아직 정확히 잘모르지만... 천천히 하다보면 나아지겠지... 아마도?