用Java实现Prim的MST

import java.util.*;

public class PrimMST {
    private static final int V = 5; // 图的顶点数

    // 找到与当前生成树相连的最小权重边所连接的顶点
    private int minKey(int[] key, boolean[] mstSet) {
        int min = Integer.MAX_VALUE;
        int minIndex = -1;

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

        return minIndex;
    }

    // 打印最小生成树
    private void printMST(int[] parent, int[][] graph) {
        System.out.println("边\t权重");
        for (int i = 1; i < V; i++) {
            System.out.println(parent[i] + " - " + i + "\t" + graph[i][parent[i]]);
        }
    }

    // 使用Prim的算法构建最小生成树
    public void primMST(int[][] graph) {
        int[] parent = new int[V]; // 存储最小生成树的父节点
        int[] key = new int[V]; // 存储顶点的权重
        boolean[] mstSet = new boolean[V]; // 记录顶点是否已经加入最小生成树

        // 初始化key数组为无穷大，mstSet数组为false
        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; // 将该顶点加入最小生成树

            // 更新与u相邻的顶点的权重
            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); // 打印最小生成树
    }

    public static void main(String[] args) {
        PrimMST mst = new PrimMST();
        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 }
        };
        mst.primMST(graph);
    }
}