[알고리즘] 크루스칼 알고리즘(최소신장트리, 최소스패닝트리)

오늘은 크루스칼 알고리즘에 대해 정리해보겠습니다.

 

크루스칼 알고리즘은 최소스패닝 트리를 구하는 알고리즘으로 이전 포스팅을 보시면 이해하시기 수월하십니다.

 

2023.12.26 - [Algorithm] - [알고리즘] 프림 알고리즘(최소신장트리, 최소스패닝트리)

[알고리즘] 프림 알고리즘(최소신장트리, 최소스패닝트리)

 

개념

 

크루스칼 알고리즘은 간선선택을 기반으로 합니다.

간선을 가중치의 오름차순으로 정렬하고 사이클을 형성하지 않을 때 간선을 선택합니다.

정점(노드)의 개수가 N개라고 했을때 간선의 갯수가 N-1이 될 때까지 이 과정을 반복합니다.

사이클 판단은 UnionFind를 사용합니다. UnionFind는 Union(x,y)연산과 Find(x)연산으로 이루어져 있습니다.

 Union연산은 x와 y를 합치는 연산이고 find연산은 그래프의 부모 노드를 찾는 연산입니다.

 

크루스칼

• 간선선택 기반
• 간선을 가중치 기준 오름차순으로 정렬하여 사이클을 형성하지 않는 선에서 선택
• UnionFind를 통해서 사이클 확인
• 사실상 정렬+UnionFind

구현예시

 

다음 그래프의 최소신장트리를 크루스칼 알고리즘을 통해 구해보겠습니다.

 

먼저 UnionFind를 위한 부모노드 배열을 설정합니다.

부모노드 배열 초기상태는 다음과 같습니다.

후에 가중치 별로 간선을 정렬해줍니다.

가중치가 같은 경우에는 from이 낮은 순서로 정렬했습니다.

이제 가중치가 낮은 순서부터 선택합니다.

 

 

간선 선택은 빨간색 동그라미로 표현하였습니다.

선택된 간선은 부모 노드 배열 값을 변경함으로 표시합니다.

 

 

 

2와 4를 연결하는 4번째 간선은 선택하지 않습니다.

2의 부모는 1 이고 4의 부모 또한 1입니다.

둘의 부모가 같기에 이 간선을 선택하면 사이클이 형성됩니다.

 

 

 

총 5개의 정점을 가진 상태에서 4개의 간선을 선택하였습니다.

부모노드 배열의 값은 모두 같아진 상태를 확인할 수 있습니다.

 

완성된 최소신장 트리는 다음과 같습니다.

모든 정점이 포함된 것을 확인할 수 있습니다.

 

과정을 요약해보겠습니다.

1. 가중치가 낮은 순으로 정렬
2. 사이클을 형성하지 않는 선에서 간선 선택
3. 정점이 N개일 때 선택한 간선의 갯수가 N-1이 될 때까지 위의 과정 반복 

 

문제 예시

 

백준 1197 최소스패닝트리 문제를 사용하였습니다.

문제 링크 : https://www.acmicpc.net/problem/1197

1197번: 최소 스패닝 트리

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

// 가중치 오름차순 정렬기준 설정
class Edge implements Comparable<Edge> {
    int from;
    int to;
    int w;


    public Edge(int from, int to, int w) {
        this.from = from;
        this.to = to;
        this.w = w;
    }

    @Override
    public int compareTo(Edge o) {
        return this.w - o.w;
    }

    @Override
    public String toString() {
        return "Edge{" +
                "from=" + from +
                ", to=" + to +
                ", w=" + w +
                '}';
    }
}

class Main {
    static ArrayList<Edge> edgeList;    // 간선정보 저장
    static int[] parents;               // 부모 노드 찾기용
    static int V, E, sum, count;

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

        st = new StringTokenizer(br.readLine());
        V = Integer.parseInt(st.nextToken());
        E = Integer.parseInt(st.nextToken());

        edgeList = new ArrayList<>();
        parents = new int[V + 1];
        for (int i = 1; i < V + 1; i++) {   // 부모노드 초기설정
            parents[i] = i;
        }

        for (int i = 0; i < E; i++) {
            st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            int C = Integer.parseInt(st.nextToken());

            edgeList.add(new Edge(A, B, C));
        }

        Kruskal();
        System.out.println(sum);
    }

    static void Kruskal() {
        Collections.sort(edgeList);             // 정렬

        for (int i = 0; i < E; i++) {           // edgeList에 저장된 간선을 차례로 가져오며
            int a = edgeList.get(i).from;       // 사용할 간선을 선택하는 과정
            int b = edgeList.get(i).to;         // a와 b를 union메서드로 사용해도 될 간선인지 확인 후
            if (union(a, b)) {                  // 사용해도 되면 sum에 가중치 값을 더하고
                sum += edgeList.get(i).w;       // count++
                count++;
            }
            if (count == V - 1) {               // count가 정점의 갯수-1이 되면 break
                break;
            }
        }
    }

    // 재귀 형태로 부모를 찾음
    public static int find(int x) {
        if (parents[x] == x) {
            return x;
        }
        return parents[x] = find(parents[x]);
    }

    // x와 y의 부모가 같으면 false 아니면 부모를 같게 한 후에(연결한 후에) true
    static boolean union(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            return false;
        } else if (x != y) {
            parents[y] = x;
        }
        return true;
    }
}

 

많이 부족한 코드입니다. 수정할 점, 잘못된 점, 개선점 보이면 말씀해주세요!!

감사합니다.