Java를 사용하여 그래프의 최소 신장 트리 알고리즘을 구현하는 방법

Java를 사용하여 그래프의 최소 스패닝 트리 알고리즘을 구현하는 방법

개념 소개:
Minimum Spanning Tree(MST)는 가중치가 있는 유향 그래프 또는 무방향 그래프에서 트리를 찾는 것을 말하며, 그래프의 모든 정점을 포함하도록 만듭니다. 그래프이고 가중치의 합이 가장 작습니다. 최소 신장 트리 알고리즘에는 여러 가지가 있으며, 가장 고전적인 두 가지 알고리즘은 Prim의 알고리즘과 Kruskal의 알고리즘입니다.

Prim 알고리즘:
Prim 알고리즘은 정점에서 시작하여 전체 최소 스패닝 트리가 생성될 때까지 점차 확장되는 포인트 기반 그리디 알고리즘입니다. 다음은 Prim의 알고리즘을 Java를 사용하여 구현하기 위한 샘플 코드입니다.

import java.util.Arrays;

public class PrimAlgorithm {

    // 表示无穷大
    private static final int INF = Integer.MAX_VALUE;

    public static void primMST(int[][] graph) {
        int vertices = graph.length;

        // 创建一个数组用来保存最小生成树的顶点
        int[] parent = new int[vertices];

        // 创建一个数组用来保存每个顶点与最小生成树的最小权值
        int[] key = new int[vertices];

        // 创建一个数组用来标记顶点是否已经加入最小生成树
        boolean[] mstSet = new boolean[vertices];

        // 初始化key数组和mstSet数组的值
        Arrays.fill(key, INF);
        Arrays.fill(mstSet, false);

        //将第一个顶点加入最小生成树
        key[0] = 0;
        parent[0] = -1;

        for (int count = 0; count < vertices - 1; count++) {
            // 选择key值最小的顶点
            int minKey = getMinKey(key, mstSet);
            mstSet[minKey] = true;

            // 更新与该顶点相邻的顶点的key值
            for (int v = 0; v < vertices; v++) {
                if (graph[minKey][v] != 0 && !mstSet[v] && graph[minKey][v] < key[v]) {
                    parent[v] = minKey;
                    key[v] = graph[minKey][v];
                }
            }
        }

        // 输出最小生成树
        printMST(parent, graph);
    }

    // 获得key值最小的顶点
    private static int getMinKey(int[] key, boolean[] mstSet) {
        int minKey = INF, minIndex = -1;
        for (int v = 0; v < key.length; v++) {
            if (!mstSet[v] && key[v] < minKey) {
                minKey = key[v];
                minIndex = v;
            }
        }
        return minIndex;
    }

    // 输出最小生成树
    private static void printMST(int[] parent, int[][] graph) {
        System.out.println("Edge   Weight");
        for (int i = 1; i < graph.length; i++) {
            System.out.println(parent[i] + " - " + i + "    " + graph[i][parent[i]]);
        }
    }

    public static void main(String[] args) {
        int[][] graph = {{0, 2, 0, 6, 0},
                         {2, 0, 3, 8, 5},
                         {0, 3, 0, 0, 7},
                         {6, 8, 0, 0, 9},
                         {0, 5, 7, 9, 0}};
        primMST(graph);
    }
}

Kruskal 알고리즘:
Kruskal 알고리즘은 Edge 기반 그리디 알고리즘으로 작은 것부터 큰 것 순으로 Edge를 선택하고, 생성되지 않는 Edge만 선택합니다. 전체 최소 신장 트리가 생성될 때까지 순환합니다. 다음은 Java를 사용하여 Kruskal 알고리즘을 구현하는 샘플 코드입니다.

import java.util.*;

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

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

class KruskalAlgorithm {
    public List<Edge> kruskalMST(List<Edge> edges, int vertices) {
        List<Edge> result = new ArrayList<>();
        Collections.sort(edges);

        int[] parent = new int[vertices];
        for (int i = 0; i < vertices; i++) {
            parent[i] = i;
        }

        int count = 0, i = 0;
        while (count < vertices - 1) {
            Edge currentEdge = edges.get(i);

            int x = find(parent, currentEdge.src);
            int y = find(parent, currentEdge.dest);

            if (x != y) {
                result.add(currentEdge);
                union(parent, x, y);
                count++;
            }

            i++;
        }

        return result;
    }

    private int find(int[] parent, int vertex) {
        if (parent[vertex] != vertex) {
            parent[vertex] = find(parent, parent[vertex]);
        }
        return parent[vertex];
    }

    private void union(int[] parent, int x, int y) {
        int xSet = find(parent, x);
        int ySet = find(parent, y);
        parent[xSet] = ySet;
    }

    public static void main(String[] args) {
        int vertices = 4;
        List<Edge> edges = new ArrayList<>();
        edges.add(new Edge(0, 1, 10));
        edges.add(new Edge(0, 2, 6));
        edges.add(new Edge(0, 3, 5));
        edges.add(new Edge(1, 3, 15));
        edges.add(new Edge(2, 3, 4));

        KruskalAlgorithm kruskal = new KruskalAlgorithm();
        List<Edge> result = kruskal.kruskalMST(edges, vertices);

        System.out.println("Edge   Weight");
        for (Edge edge : result) {
            System.out.println(edge.src + " - " + edge.dest + "    " + edge.weight);
        }
    }
}

위는 Java를 사용하여 Prim 알고리즘과 Kruskal 알고리즘을 구현하는 샘플 코드입니다. 둘 다 그래프의 최소 스패닝 트리 알고리즘을 구현하는 고전적인 방법입니다. 이러한 코드를 배우고 이해함으로써 Java를 사용하여 그래프의 최소 스패닝 트리 알고리즘을 구현하는 방법을 더 잘 이해하고 마스터할 수 있습니다.

위 내용은 Java를 사용하여 그래프의 최소 신장 트리 알고리즘을 구현하는 방법의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!