[알고리즘] Kruskal 알고리즘

이 글은 혼자 학습한 내용을 바탕으로 작성되었습니다.

틀리거나 잘못된 정보가 있을 수 있습니다.

댓글로 알려주시면 수정하도록 하겠습니다.

---

1. Kruskal 알고리즘이란

그래프의 간선에 비용이 있는 경우 해당 그래프이 모든 정점을 연결하는 최소 비용으로 연결하는 최소비용 신장트리를 찾는 알고리즘 입니다.

 

신장트리

그래프의 모든 정점을 포함하고 정점들은 간선으로 연결되어 있으면서 사이클이 존재하지 않는 그래프를 말합니다.

그래프

그래프의 신장트리

위 이미지의 그래프가 그래프의 신장트리가 됩니다. 수많은 신장트리 중에서 연결된 간선의 비용이 최소가 되는 신장트리를 바로 최소비용 신장트리라고 하며 Kruskal 알고리즘을 통해 해당 그래프를 찾을 수 있습니다.

 

2. Kruskal 알고리즘 고려사항

• 최소 비용의 간선을 선택하는 과정을 최소화 하기위해 간선을 오름차순으로 정렬 한다.
• Kruskal 알고리즘은 임의의 정점을 기준으로 최소 비용의 간선을 선택해 연결해 나가는 알고리즘으로 임의의 정점에 연결된 정점을 선택 했을 때 해당 정점이 어느 집합의 원소인지를 확인하는 과정이 필요

 

3. Kruskal 알고리즘 방법

• 선택 되지 않은 여러 간선 중 비용이 가장 적은 간선 부터 선택해 나간다.
• 간선 선택 과정에서 사이클이 발생하면 해당 간선은 선택하지 않는다.
• 신장트리는 N개의 정점(모든 정점)을 연결하여 만들어 지므로 N-1개의 간선이 선택되면 실행을 종료 한다.

그래프와 정렬된 간선Table 그리고 해당 정점이 포함된 집합을 알 수 있는 Parent Table이 위 이미지 처럼 준비가 되었습니다.

 

최소 비용의 정점인 5번 정점과 4번 정점을 연결하는 간선을 선택 합니다. 이후 5번 정점은 4번 정점과 동일한 집합에 속하게 되므로 Parent Table의 5번의 값을 4로 변경하여 5번 정점은 4번 정점과 같은 집합에 속하는 것을 표시합니다.

 

2번째 최소 비용의 정점인 1번 정점과 2번 정점을 연결하는 간선을 선택 합니다. 이후 2번 정점은 1번 정점과 동일한 집합에 속하게 되므로 Parent Table의 2번의 값을 1로 변경하여 2번 정점은 1번 정점과 같은 집합에 속하는 것을 표시합니다.

 

3번째 최소 비용의 정점인 3번 정점과 5번 정점을 연결하는 간선을 선택 합니다. 이후 5번 정점은 3번 정점과 동일한 집합에 속하게 된다. 그러나 이미 5번 정점은 4번 정점 집합에 속해 있으므로 4번 정점 집합을 3번 정점 집합에 속하게 하는 것과 같다. 그래서 4번 정점이 3번 정점에 속하는 것을 표시합니다.

 

4번째 최소 비용의 정점인 1번 정점과 4번 정점을 연결하는 간선을 선택 합니다. 이후 4번 정점은 1번 정점과 동일한 집합에 속하게 된다. 그러나 이미 4번 정점은 3번 정점 집합에 속해 있으므로 3번 정점 집합을 1번 정점 집합에 속하게 하는 것과 같다. 그래서 3번 정점이 1번 정점에 속하는 것을 표시합니다.

 

신장트리는 N개의 정점(모든 정점)을 연결하여 만들어 지므로 N-1개의 간선이 선택되면 실행을 종료 한다.

 

최종 신장트리 및 최소비용

위 그래프의 정점이 총 5개이고 연결된 간선이 4개이므로 실행을 종료하고 찾은 그래프가 최소비용 신장 트리가 되며

최소 비용은 47이 된다.

 

4. 구현 코드

전체 코드는 Git에 있습니다.

public class Main {
    private static int vertexCount;
    private static int edgeCount;
    private static int[][] graph;
    private static int[] parent;

    public static void main(String[] args) {
        vertexCount = 5;
        edgeCount = 7;

        graph = new int[][]{{5, 4, 8}, {1, 2, 10}, {3, 5, 13}, {1, 4, 16},
                            {2, 3, 19}, {2, 5, 25}, {3, 1, 30}};
        Arrays.sort(graph, Comparator.comparingInt(o -> o[2]));

        parent = new int[vertexCount];
        for (int i = 0; i < vertexCount; i++)
            parent[i] = i;

        int cost = 0;
        for (int i = 0; i < edgeCount; i++) {
            if (getParentValue(graph[i][0] - 1) != getParentValue(graph[i][1] - 1)) {
                merge(graph[i][0] - 1, graph[i][1] - 1);
                cost += graph[i][2];
                continue;
            }
        }

        System.out.println(cost);
    }

    public static int getParentValue(int node) {
        if (parent[node] == node)
            return node;
        else
            return getParentValue(parent[node]);
    }

    public static void merge(int startNode, int endNode) {
        int startParent = getParentValue(startNode);
        int endParent = getParentValue(endNode);

        if (startParent > endParent)
            parent[startParent] = endParent;
        else
            parent[endParent] = startParent;
    }
}