Java 实现 Prim 算法构建最小生成树

以下是 Java 代码实现 Prim 算法建立最小生成树：

import java.util.*;

public class PrimAlgorithm {
    private int V; // 图的顶点数
    private int[] parent; // 最小生成树的父节点
    private int[] key; // 每个节点到最小生成树的距离
    private boolean[] mstSet; // 最小生成树集合
    private int[][] graph; // 图的邻接矩阵

    public PrimAlgorithm(int V, int[][] graph) {
        this.V = V;
        this.graph = graph;
        parent = new int[V];
        key = new int[V];
        mstSet = new boolean[V];
        Arrays.fill(key, Integer.MAX_VALUE);
        Arrays.fill(mstSet, false);
    }

    // 执行Prim算法
    public void prim() {
        key[0] = 0; // 从第一个节点开始构建最小生成树
        parent[0] = -1; // 第一个节点没有父节点

        for (int i = 0; i < V - 1; i++) {
            int u = getMinimumKeyVertex();
            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];
                }
            }
        }

        // 输出最小生成树
        System.out.println('Edge 	Weight');
        for (int i = 1; i < V; i++) {
            System.out.println(parent[i] + ' - ' + i + '	' + graph[i][parent[i]]);
        }
    }

    // 获取到最小生成树距离最小的节点
    private int getMinimumKeyVertex() {
        int minKey = Integer.MAX_VALUE;
        int minIndex = -1;

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

        return minIndex;
    }

    public static void main(String[] args) {
        int V = 5;
        int[][] graph = new int[][]{{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}};

        PrimAlgorithm prim = new PrimAlgorithm(V, graph);
        prim.prim();
    }
}

输出结果为：

Edge    Weight
0 - 1   2
1 - 2   3
0 - 3   6
1 - 4   5