prim算法Java

以下是使用Java实现Prim算法的示例代码：

import java.util.Arrays;

public class PrimAlgorithm {
    private static final int INF = Integer.MAX_VALUE; // 表示两个顶点之间没有边

    public void prim(int[][] graph) {
        int numVertex = graph.length; // 图中顶点的数量
        int[] lowCost = new int[numVertex]; // 存储当前顶点到最小生成树的最短距离
        int[] closest = new int[numVertex]; // 存储当前顶点到最小生成树的最短距离的那个顶点
        boolean[] visited = new boolean[numVertex]; // 存储当前顶点是否已经被访问过

        // 初始化lowCost和closest数组
        for (int i = 1; i < numVertex; i++) {
            lowCost[i] = graph[0][i];
            closest[i] = 0;
            visited[i] = false;
        }

        visited[0] = true; // 将第一个顶点标记为已访问

        // 依次将剩余的n-1个顶点加入到最小生成树中
        for (int i = 1; i < numVertex; i++) {
            int minCost = INF;
            int nextVertex = -1;

            // 从当前未访问的顶点中找到到最小生成树距离最短的那个顶点
            for (int j = 1; j < numVertex; j++) {
                if (!visited[j] && lowCost[j] < minCost) {
                    minCost = lowCost[j];
                    nextVertex = j;
                }
            }

            // 将找到的顶点加入到最小生成树中
            visited[nextVertex] = true;

            // 更新lowCost和closest数组
            for (int j = 1; j < numVertex; j++) {
                if (!visited[j] && graph[nextVertex][j] < lowCost[j]) {
                    lowCost[j] = graph[nextVertex][j];
                    closest[j] = nextVertex;
                }
            }
        }

        // 输出最小生成树
        for (int i = 1; i < numVertex; i++) {
            System.out.println("Edge: " + closest[i] + " - " + i + ", weight: " + graph[closest[i]][i]);
        }
    }

    public static void main(String[] args) {
        int[][] graph = {
                {0, 6, 1, 5, INF, INF},
                {6, 0, 5, INF, 3, INF},
                {1, 5, 0, 5, 6, 4},
                {5, INF, 5, 0, INF, 2},
                {INF, 3, 6, INF, 0, 6},
                {INF, INF, 4, 2, 6, 0}
        };

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