[java] 크루스칼 알고리즘의 동작 원리

04 Dec 2023

java

크루스칼 알고리즘은 그래프의 최소 신장 트리를 찾는 알고리즘 중 하나입니다. 이 알고리즘은 간선의 가중치를 기준으로 최소 신장 트리를 구축하기 때문에, 가중치가 있는 비방향 그래프에서 주로 사용됩니다.

크루스칼 알고리즘의 동작 원리는 다음과 같습니다:

그래프의 간선들을 가중치 순으로 정렬합니다.
가중치가 가장 작은 간선부터 선택하여 그래프에 추가합니다.
추가된 간선이 사이클을 만들지 않으면, 즉, 그래프에 이미 포함된 노드들 사이에 연결이 없으면 해당 간선을 최소 신장 트리에 포함시키고, 그렇지 않으면 해당 간선을 무시합니다.
모든 간선을 탐색할 때까지 2~3 과정을 반복합니다.

이 알고리즘을 구현하기 위해서는 다음과 같은 자료구조가 필요합니다:

Union-Find(Disjoint Set) 자료구조: 간선을 추가할 때 사이클을 확인하기 위해 사용됩니다.
우선순위 큐(Priority Queue): 간선의 가중치를 기준으로 정렬하기 위해 사용됩니다.

다음은 자바로 구현된 크루스칼 알고리즘의 예시 코드입니다:

import java.util.*;

class Edge implements Comparable<Edge> {
    int src, dest, weight;
    
    public Edge(int src, int dest, int weight) {
        this.src = src;
        this.dest = dest;
        this.weight = weight;
    }
    
    @Override
    public int compareTo(Edge other) {
        return this.weight - other.weight;
    }
}

class Graph {
    List<Edge> edges;
    
    public Graph() {
        edges = new ArrayList<>();
    }
    
    public void addEdge(int src, int dest, int weight) {
        Edge edge = new Edge(src, dest, weight);
        edges.add(edge);
    }
    
    public List<Edge> kruskalMST() {
        List<Edge> result = new ArrayList<>();
        Collections.sort(edges);
        
        DisjointSet ds = new DisjointSet();
        
        for (Edge edge : edges) {
            int srcParent = ds.find(edge.src);
            int destParent = ds.find(edge.dest);
            
            if (srcParent != destParent) {
                result.add(edge);
                ds.union(srcParent, destParent);
            }
        }
        
        return result;
    }
}

class DisjointSet {
    int[] parent;
    
    public DisjointSet() {
        parent = new int[100]; // 적절한 크기로 초기화해야 함
        for (int i = 0; i < parent.length; i++) {
            parent[i] = i;
        }
    }
    
    public int find(int node) {
        if (parent[node] == node) {
            return node;
        }
        return find(parent[node]);
    }
    
    public void union(int node1, int node2) {
        int parent1 = find(node1);
        int parent2 = find(node2);
        
        parent[parent1] = parent2;
    }
}

public class KruskalAlgorithm {
    public static void main(String[] args) {
        Graph graph = new Graph();
        
        graph.addEdge(0, 1, 10);
        graph.addEdge(0, 2, 6);
        graph.addEdge(0, 3, 5);
        graph.addEdge(1, 3, 15);
        graph.addEdge(2, 3, 4);
        
        List<Edge> mst = graph.kruskalMST();
        
        System.out.println("Minimum Spanning Tree:");
        for (Edge edge : mst) {
            System.out.println(edge.src + " - " + edge.dest + " : " + edge.weight);
        }
    }
}

위 코드에서 Graph 클래스는 그래프를 나타내며, Edge 클래스는 간선을 나타냅니다. kruskalMST 메소드에서는 크루스칼 알고리즘을 구현하고 최소 신장 트리를 반환합니다.

이러한 방식으로 크루스칼 알고리즘을 Java로 구현할 수 있습니다. 자세한 내용은 문서 참고 바랍니다.

참고 자료: