prim算法java

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

import java.util.*;

public class PrimAlgorithm {
    private int V; // 图中顶点的数量
    private int[][] graph; // 图的邻接矩阵

    public PrimAlgorithm(int v, int[][] g) {
        V = v;
        graph = g;
    }

    // 执行 Prim 算法，返回最小生成树的权重和
    public int prim() {
        int[] dist = new int[V]; // 存储每个顶点到最小生成树的最短距离
        boolean[] visited = new boolean[V]; // 存储每个顶点是否已经加入最小生成树
        Arrays.fill(dist, Integer.MAX_VALUE); // 初始化距离数组为最大值
        dist[0] = 0; // 从第一个顶点开始构建最小生成树

        int sum = 0; // 最小生成树的权重和
        for (int i = 0; i < V; i++) {
            int u = getMinVertex(dist, visited); // 获取到最小距离的顶点
            visited[u] = true; // 将该顶点加入最小生成树

            sum += dist[u]; // 将该顶点的距离加入最小生成树的权重和

            // 更新与该顶点相邻的顶点的距离
            for (int v = 0; v < V; v++) {
                if (graph[u][v] != 0 && !visited[v] && graph[u][v] < dist[v]) {
                    dist[v] = graph[u][v];
                }
            }
        }

        return sum;
    }

    // 获取到距离最小的顶点
    private int getMinVertex(int[] dist, boolean[] visited) {
        int minDist = Integer.MAX_VALUE;
        int minVertex = -1;
        for (int i = 0; i < V; i++) {
            if (!visited[i] && dist[i] < minDist) {
                minDist = dist[i];
                minVertex = i;
            }
        }
        return minVertex;
    }

    public static void main(String[] args) {
        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(5, graph);
        int sum = prim.prim();
        System.out.println("最小生成树的权重和为：" + sum);
    }
}

注意：这里使用的是邻接矩阵来表示图，如果使用邻接表或其他数据结构来表示图，则需要对应地修改代码。