[알고리즘] Kruskal 알고리즘이란

Kruskal 알고리즘이란?

크루스칼 알고리즘은 그래프의 모든 정점을 최소 비용으로 연결하는 최적해를 구하는 것으로 부분 그래프 중에서 가중치의 합이 최소인 트리인 최소 신장 트리(MST, Minimum Spanning Tree)를 구하는데 적합한 알고리즘이다.

Spanning Tree란?

신장 트리는 그래프 상의 모든 정점이 사이클 없이 연결된 최소 부분 그래프를 뜻한다.

• 그래프에서 간선의 수가 가장 적다.
• 가장 작은 간선의 수는 n개의 정점을 가지는 그래프에서 (n-1)개일 경우이다.
• 이때, 그래프의 형태는 필연적으로 트리 형태가 된다.
• 이중 간선의 가중치의 합이 최소인 경우를 최소 신장 트리(MST, Minimum Spanning Tree)라고 한다.

MST의 활용
도시들을 모두 연결하면서 도로의 길이가 최소가 되도록 하는 문제
단자들을 모두 연결하면서 전선의 길이가 가장 최소가 되도록 하는 문제
전화선의 길이가 최소가 되도록 전화 케이블 망을 구성하는 문제
파이프를 모두 연결하면서 파이프의 총 길이가 최소가 되도록 하는 문제

크루스칼 알고리즘 과정

1. 그래프의 간선들을 가중치를 기준으로 오름차순으로 정렬한다.
2. 가장 낮은 가중치부터 선택해 간선을 추가해준다.
3. 추가된 간선과 사이클을 형성하는 간선을 제외한다.
4. 추가된 간선의 개수가 정점의 개수 - 1이 될 경우, 종료한다.

크루스칼 알고리즘 과정 코드로 보기

그래프의 간선들을 가중치를 기준으로 오름차순으로 정렬한다.

// 간선 정보 입력
List<Edge> edges = new ArrayList<>();
for (int i = 0; i < E; i++) {
    stringTokenizer = new StringTokenizer(bufferedReader.readLine());
    int vertexA = Integer.parseInt(stringTokenizer.nextToken());
    int vertexB = Integer.parseInt(stringTokenizer.nextToken());
    int weight = Integer.parseInt(stringTokenizer.nextToken());

    edges.add(new Edge(vertexA, vertexB, weight));
}

// 가중치 기준으로 오름차순 정렬
edges.sort((o1, o2) -> o1.weight - o2.weight);

가장 낮은 가중치부터 선택해 간선을 추가해준다.

// 최소의 간선만 선택해서 가중치를 누적시킨다.
for (int i = 0; i < edges.size(); i++) {
    Edge edge = edges.get(i);
    int cur = edge.vertexA;
    int next = edge.vertexB;
    int weight = edge.weight;
}

추가된 간선과 사이클을 형성하는 간선을 제외한다.

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

    // 사이클이 아닌 경우에 가중치를 누적시킨다.
    if (findParent(cur) != findParent(next)) {
        unionParent(cur, next);
        result += weight;
        cnt++;
    }
}

사이클 형성 여부는 양끝 정점이 동일한 점과 연결되었는지를 검사해 확인하고 가중치를 누적시킨 후에는 정점을 연결시켜 줄 수 있도록 한다.

// 정점의 연결점 초기화는 자기 자신으로 해준다.
int[] parent = new int[V + 1];
for (int i = 1; i <= V; i++) {
    parent[i] = i;
}

// 정점의 연결을 확인한다.
private static int findParent(int vertex) {
    if (parent[vertex] == vertex) return vertex;
    return parent[vertex] = findParent(parent[vertex]);
}

// 정점끼리 연결 시킨다.
private static void unionParent(int a, int b) {
    a = findParent(a);
    b = findParent(b);

    parent[b] = a;
}

추가된 간선의 개수가 정점의 개수 - 1이 될 경우, 종료한다.

for (int i = 0; i < E; i++) {
    ...
    
    // 가장 작은 간선의 수는 정점의 수 - 1이다.
    if (cnt == V - 1) break;
}

크루스칼 알고리즘 구현 문제 - 백준 1197번 

import java.io.*;
import java.util.*;

public class Main {
    static List<Edge> edges = new ArrayList<>();
    static int[] parent;

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine());

        // 정점의 개수
        int V = Integer.parseInt(stringTokenizer.nextToken());
        // 간선의 개수
        int E = Integer.parseInt(stringTokenizer.nextToken());

        // 그래프 생성
        parent = new int[V + 1];
        for (int i = 1; i <= V; i++) {
            parent[i] = i;
        }

        // 간선 정보 입력
        for (int i = 0; i < E; i++) {
            stringTokenizer = new StringTokenizer(bufferedReader.readLine());
            int vertexA = Integer.parseInt(stringTokenizer.nextToken());
            int vertexB = Integer.parseInt(stringTokenizer.nextToken());
            int weight = Integer.parseInt(stringTokenizer.nextToken());

            edges.add(new Edge(vertexA, vertexB, weight));
        }

        // 가중치 기준으로 오름차순 정렬
        edges.sort((o1, o2) -> o1.weight - o2.weight);

        int result = 0;
        int cnt = 0;
        // 최소의 간선만 선택해서 가중치를 누적시킨다.
        for (int i = 0; i < edges.size(); i++) {
            Edge edge = edges.get(i);
            int cur = edge.vertexA;
            int next = edge.vertexB;
            int weight = edge.weight;

            // 사이클이 아닌 경우에 가중치를 누적시킨다.
            if (findParent(cur) != findParent(next)) {
                unionParent(cur, next);
                result += weight;
                cnt++;
            }

            if (cnt == V - 1) break;
        }

        System.out.println(result);
    }

    private static int findParent(int vertex) {
        if (parent[vertex] == vertex) return vertex;
        return parent[vertex] = findParent(parent[vertex]);
    }

    private static void unionParent(int a, int b) {
        a = findParent(a);
        b = findParent(b);

        parent[b] = a;
    }

    static class Edge {
        int vertexA;
        int vertexB;
        int weight;

        public Edge(int vertexA, int vertexB, int weight) {
            this.vertexA = vertexA;
            this.vertexB = vertexB;
            this.weight = weight;
        }
    }
}