[알고리즘] Kruscal 크루스칼 알고리즘

최소 신장 트리 (MST, Minimum Spanning Tree) 를 만들기 위한 대표적인 알고리즘 중 하나이다

 

 

특징

 

1. 그리디 알고리즘

• 크루스칼 알고리즘은 그리디 알고리즘의 일종으로 매 순간 최적의 선택을 하면서 전체 최적해를 찾는다
• 이 말은 즉, 간선의 가중치가 가장 작은 것부터 차례대로 선택하여 최소 신장 트리를 구성

 

2. 간선 중심!

• 간선의 가중치에 기반하여 간선을 선택한다
• 그래서 간선을 정렬한 후 가장 가중치가 작은 간선부터 선택하는 방식이다

 

3. 간선 수가 적을 때 효율적

• 간선의 수가 정점의 수에 비해 적을때 크루스칼 알고리즘이 효율적으로 동작한다
• 왜냐하면 전체 간선을 정렬한 후 선택하는 방식이기 때문이다

 

 

과정

1. 초기 상태는 정점은 서로 연결되어 있지 않는 상태이다

2. 간선을 하나씩 추가하면서 MST를 만든다

2-1. 크기가 가장 작은 간선부터 모든 간선을 본다 

2-2. 가중치를 이용해 간선을 오름차순으로 정렬한다

-> 1, 2, 2, 4, 5, 7, 7

 

2-3. 가중치가 가장 적은 간선 부터 그래프에 추가한다 

2-4. 추가 할때 MST에 사이클이 생기는지 확인 -> 여기에서 유니온 파인드 알고리즘을 이용함

2-5. 추가 할때 사이클이 생기지 않는다면 추가

2-6. 추가할때 사이클이 생긴다면 추가 하지않고 다음 간선을 본다

 

3. 이런식으로 2번을 반복하다가 정점이 다 이어져 있으면 종료를 한다 -> 이게 MST가 되는것이다.

짜잔~ 완성!

 

 

코드 표현

 

import java.util.*;

public class Solution {
    static int nodeCount = 5;
    static int[] parents;


    public static void main(String[] args) throws Exception {
        Edge[] edgeArray = new Edge[7];

        edgeArray[0] = new Edge(1, 4, 1);
        edgeArray[1] = new Edge(1, 3, 7);
        edgeArray[2] = new Edge(1, 2, 7);
        edgeArray[3] = new Edge(2, 5, 2);
        edgeArray[4] = new Edge(3, 4, 2);
        edgeArray[5] = new Edge(3, 5, 4);
        edgeArray[6] = new Edge(4, 5, 5);

        Arrays.sort(edgeArray);
        init();

        int weightSum = 0;
        for (Edge edge : edgeArray) {
            if (union(edge.nodeA, edge.nodeB)) {
                System.out.println(edge.nodeA + " -> " + edge.nodeB);
                weightSum += edge.weight;
            }
        }
        System.out.println(weightSum);
    }

    public static void init() {
        parents = new int[nodeCount + 1];
        for (int i = 1; i <= nodeCount; i++) {
            parents[i] = i;
        }
    }

    public static int findRoot(int a) {
        if (parents[a] == a) {
            return a;
        }

        return parents[a] = findRoot(parents[a]);
    }

    public static boolean union(int a, int b) {
        int aRoot = findRoot(a);
        int bRoot = findRoot(b);

        if (aRoot == bRoot) {
            return false;
        }
        parents[aRoot] = bRoot;
        return true;
    }


}

class Edge implements Comparable<Edge> {

    int nodeA;
    int nodeB;
    int weight;

    public Edge(int nodeA, int nodeB, int weight) {
        this.nodeA = nodeA;
        this.nodeB = nodeB;
        this.weight = weight;
    }

    public int compareTo(Edge o) {
        return this.weight - o.weight;
    }
}

 

 

코드 실행 화면