[알고리즘]크루스칼 알고리즘 자바 구현법

들어가며

1197번: 최소 스패닝 트리

위 문제를 풀면서 최소 스패닝 트리를 만드는 크루스칼 알고리즘을 작성해보았다.

 

코드

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

public class 크루스칼 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] s = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int v = s[0];
        int e = s[1];
        Graph graph = new Graph(v,e);
        for (int i = 0; i < e; i++){
            int[] s1 = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
            int start = s1[0];
            int end = s1[1];
            int weight = s1[2];
            graph.push(new Edge(start,end,weight));
        }
        ArrayList<Edge> result = graph.kru(v);
    }

    private static class Graph{
        private ArrayList<Edge> graph = new ArrayList<>();
        private int[] parents;
        public Graph(int v, int e){
            parents = new int[v+1];
            for (int i = 1; i <= v; i++) {
                parents[i] = i;
            }
        }
        public void push(Edge edge){
            graph.add(edge);
        }

        public ArrayList<Edge> kru(int v){
            Collections.sort(graph);
            ArrayList<Edge> result = new ArrayList<>();

            for (var i : graph){
                int start = i.start;
                int end = i.end;
                double weight = i.weight;

                int startRoot = find(start);
                int endRoot = find(end);
                if (startRoot != endRoot){
                    result.add(i);
                    union(start,end);
                }
            }
            return result;
        }
        private int find(int current){
            if (parents[current] == current){
                return current;
            }
            return parents[current]= find(parents[current]);
        }
        private void union(int a, int b){
            int rootA = find(a);
            int rootB = find(b);
            if (rootA != rootB) {
                parents[rootB] = rootA;
            }
        }
    }

    private static class Edge implements Comparable<Edge>{
        int start;
        int end;
        double weight;

        public Edge(int start, int end, double weight) {
            this.start = start;
            this.end = end;
            this.weight = weight;
        }

        @Override
        public int compareTo(Edge o) {
            return Double.compare(weight,o.weight);
        }
    }
}

 

설명

크루스칼의 동작방식을 짧게 요약하면 다음과 같다.

1. 모든 간선을 가중치 기준으로 오름차순 정렬
2. 가장 작은 간선부터 선택하며, 사이클이 생기지 않도록 연결
3. Union-Find 자료구조를 사용하여 사이클 여부를 효율적으로 확인

이를 수도 코드로 표현하면 다음과 같다.

MST-KRUSKAL(G, w) // w는 가중치 리스트
	A = []
	for G.V 에 존재하는 모든 정점 v 
		MAKE-SET(v)
	G.E의 간선들로 이루어진 한 개의 리스트를 만든다.
	간선들의 리스트를 가중치 w에 따라 단조 감소 순서로 정렬한다.
	for 정렬된 리스트를 가중치 w에 따라 단조 감소 순서로 정렬한다.
		if FIND-SET(u) != FIND-SET(v)
			A = A U {(u,v)}
			UNION(u,v)
	retrun A

사실상 위 수도 코드를 그대로 옮긴 것이 본문의 코드라고 할 수 있다.