[java] 섬 연결하기 알고리즘

04 Dec 2023

java

섬 연결하기 알고리즘은 그래프 이론에서 사용되는 알고리즘 중의 하나입니다. 이 알고리즘은 그래프에서 모든 정점을 최소 비용으로 연결하는 최소 비용 신장 트리(Minimum Cost Spanning Tree)를 구하는 문제를 해결합니다.

Kruskal 알고리즘

Kruskal 알고리즘은 섬 연결하기 문제를 해결하는 아주 효율적인 알고리즘 중의 하나입니다. 이 알고리즘은 그리디 알고리즘의 한 예로, 간선을 가중치 순으로 정렬한 뒤, 순서대로 선택하여 신장 트리를 형성하는 방식으로 동작합니다.

Kruskal 알고리즘의 동작 과정은 다음과 같습니다.

그래프의 간선을 가중치 순으로 정렬합니다.
가중치가 가장 작은 간선부터 선택하여 현재 신장 트리에 추가합니다. 이때 간선이 추가되었을 때 신장 트리에 사이클이 형성되지 않는다면 해당 간선을 선택합니다.
모든 정점이 포함될 때까지 2번의 과정을 반복합니다.

Kruskal 알고리즘을 Java로 구현한 예시 코드는 다음과 같습니다.

import java.util.*;

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

class Graph {
    int V, E;
    Edge[] edges;
    
    Graph(int V, int E) {
        this.V = V;
        this.E = E;
        edges = new Edge[E];
        for (int i = 0; i < E; i++) {
            edges[i] = new Edge();
        }
    }
    
    int find(int[] parent, int i) {
        if (parent[i] == -1)
            return i;
        return find(parent, parent[i]);
    }
    
    void union(int[] parent, int x, int y) {
        int xset = find(parent, x);
        int yset = find(parent, y);
        parent[xset] = yset;
    }
    
    void kruskalMST() {
        Edge[] result = new Edge[V];
        int e = 0;
        int i = 0;
        for (i = 0; i < V; i++) {
            result[i] = new Edge();
        }
        
        Arrays.sort(edges);
        
        int[] parent = new int[V];
        Arrays.fill(parent, -1);
        
        i = 0;
        while (e < V - 1) {
            Edge next_edge = edges[i++];
            
            int x = find(parent, next_edge.src);
            int y = find(parent, next_edge.dest);
            
            if (x != y) {
                result[e++] = next_edge;
                union(parent, x, y);
            }
        }
        
        System.out.println("Edge \tWeight");
        for (i = 0; i < e; i++) {
            System.out.println(result[i].src + " - " + result[i].dest + "\t" + result[i].weight);
        }
    }
}

public class Main {
    public static void main(String[] args) {
        int V = 4; // 정점의 수
        int E = 5; // 간선의 수
        
        Graph graph = new Graph(V, E);
        
        graph.edges[0].src = 0;
        graph.edges[0].dest = 1;
        graph.edges[0].weight = 10;
        
        graph.edges[1].src = 0;
        graph.edges[1].dest = 2;
        graph.edges[1].weight = 6;
        
        graph.edges[2].src = 0;
        graph.edges[2].dest = 3;
        graph.edges[2].weight = 5;
        
        graph.edges[3].src = 1;
        graph.edges[3].dest = 3;
        graph.edges[3].weight = 15;
        
        graph.edges[4].src = 2;
        graph.edges[4].dest = 3;
        graph.edges[4].weight = 4;
        
        graph.kruskalMST();
    }
}

위의 예시 코드는 4개의 정점과 5개의 간선을 가지는 그래프에서 Kruskal 알고리즘을 이용하여 최소 비용 신장 트리를 구하는 예시입니다. 출력 결과는 다음과 같습니다.

Edge    Weight
- 3    4
- 3    5
- 1    10

추가로, Kruskal 알고리즘의 시간 복잡도는 O(ElogV)입니다.

참고 자료

Kruskal’s algorithm