Java로 구현하는 최소 신장 트리(Minimum Spanning Tree) 알고리즘

최소 신장 트리(Minimum Spanning Tree, MST)는 그래프 이론에서 중요한 개념으로, 가중치가 부여된 무향 그래프에서 모든 노드를 최소한의 비용으로 연결하는 부분 그래프입니다. MST는 네트워크 설계, 클러스터링, 경로 최적화 등 다양한 분야에서 응용됩니다. Java 프로그래밍 언어는 객체 지향적 특성과 풍부한 라이브러리를 통해 MST 알고리즘을 구현하기에 적합한 환경을 제공합니다. 본문에서는 Kruskal과 Prim 두 가지 MST 알고리즘을 Java로 구현하는 방법을 소개합니다.

• Kruskal의 알고리즘

Kruskal의 알고리즘은 가장 가벼운 가중치를 가진 간선부터 차례대로 선택하여 MST를 구성합니다. 이 과정에서 사이클이 형성되지 않도록 주의해야 합니다. 이 알고리즘의 구현은 분리 집합(disjoint sets)을 이용하여 사이클을 감지하고 처리합니다.

import java.util.*;

class Graph {
    class Edge implements Comparable<Edge> {
        int src, dest, weight;

        public int compareTo(Edge compareEdge) {
            return this.weight - compareEdge.weight;
        }
    }

    class subset {
        int parent, rank;
    }

    int V, E;
    Edge edge[];

    Graph(int v, int e) {
        V = v;
        E = e;
        edge = new Edge[E];
        for (int i = 0; i < e; ++i)
            edge[i] = new Edge();
    }

    int find(subset subsets[], int i) {
        if (subsets[i].parent != i)
            subsets[i].parent = find(subsets, subsets[i].parent);
        return subsets[i].parent;
    }

    void Union(subset subsets[], int x, int y) {
        int xroot = find(subsets, x);
        int yroot = find(subsets, y);

        if (subsets[xroot].rank < subsets[yroot].rank)
            subsets[xroot].parent = yroot;
        else if (subsets[xroot].rank > subsets[yroot].rank)
            subsets[yroot].parent = xroot;
        else {
            subsets[yroot].parent = xroot;
            subsets[xroot].rank++;
        }
    }

    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(edge);

        subset subsets[] = new subset[V];
        for (i = 0; i < V; ++i)
            subsets[i] = new subset();

        for (int v = 0; v < V; ++v) {
            subsets[v].parent = v;
            subsets[v].rank = 0;
        }

        i = 0;
        while (e < V - 1) {
            Edge next_edge = new Edge();
            next_edge = edge[i++];

            int x = find(subsets, next_edge.src);
            int y = find(subsets, next_edge.dest);

            if (x != y) {
                result[e++] = next_edge;
                Union(subsets, x, y);
            }
        }

        for (i = 0; i < e; ++i)
            System.out.println(result[i].src + " -- " + result[i].dest + " == " + result[i].weight);
    }
}

 

 

• Prim의 알고리즘

Prim의 알고리즘은 시작 정점에서부터 점진적으로 MST를 확장해 나가는 방법을 사용합니다. 가장 적은 가중치를 가진 간선을 선택하면서, 이미 선택된 정점들과 연결된 간선들 중에서 최소 비용의 간선을 찾아 MST에 추가합니다.

 

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

class Graph {
    private int V;

    int minKey(int key[], Boolean mstSet[]) {
        int min = Integer.MAX_VALUE, minIndex = -1;
        for (int v = 0; v < V; v++)
            if (!mstSet[v] && key[v] < min) {
                min = key[v];
                minIndex = v;
            }
        return minIndex;
    }

    void printMST(int parent[], int graph[][]) {
        System.out.println("Edge \tWeight");
        for (int i = 1; i < V; i++)
            System.out.println(parent[i] + " - " + i + "\t" + graph[i][parent[i]]);
    }

    void primMST(int graph[][]) {
        int parent[] = new int[V];
        int key[] = new int[V];
        Boolean mstSet[] = new Boolean[V];
        for (int i = 0; i < V; i++) {
            key[i] = Integer.MAX_VALUE;
            mstSet[i] = false;
        }

        key[0] = 0;
        parent[0] = -1;

        for (int count = 0; count < V - 1; count++) {
            int u = minKey(key, mstSet);
            mstSet[u] = true;

            for (int v = 0; v < V; v++)
                if (graph[u][v] != 0 && !mstSet[v] && graph[u][v] < key[v]) {
                    parent[v] = u;
                    key[v] = graph[u][v];
                }
        }

        printMST(parent, graph);
    }
}

 

Kruskal과 Prim 알고리즘은 각각의 특성과 장단점이 있으며, 사용하는 그래프의 유형(밀집 그래프나 희소 그래프)과 문제의 요구 사항에 따라 적절한 알고리즘을 선택해야 합니다. Java로 이러한 최소 신장 트리 알고리즘을 구현하면, 복잡한 그래프 문제를 효과적으로 해결할 수 있으며, 이는 프로그래밍 능력과 함께 문제 해결 능력을 향상시키는 데 도움이 됩니다.