java最小生成树prim算法

Java中Prim算法是一种用于在加权无向图中查找最小生成树的算法。它通过贪心算法逐步扩展生成树，每次选取距离生成树最近的顶点，直到生成完整棵树。以下是Prim算法的基本思路：

1. 从图中任意一个顶点开始，将其加入生成树中。
2. 将该顶点的所有未被访问过的邻居加入一个最小堆中。
3. 从堆中选择一个距离生成树最近的顶点加入生成树，并将该顶点的未被访问过的邻居加入堆中。
4. 重复步骤3，直到生成完整棵树。

下面是Java代码实现Prim算法：

import java.util.*;

public class Prim {
    public static int prim(int[][] graph, int n) {
        int[] dist = new int[n];  // 距离数组
        boolean[] visited = new boolean[n];  // 标记是否访问过
        int ans = 0;  // 最小生成树的总权值
        Arrays.fill(dist, Integer.MAX_VALUE);  // 初始化距离数组为最大值
        dist = 0;  // 从第一个点开始遍历
        PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.comparingInt(a -> dist[a]));  // 最小堆

        pq.offer(0);  // 将第一个点加入最小堆中
        while (!pq.isEmpty()) {
            int cur = pq.poll();
            if (visited[cur]) continue;  // 如果已经访问过，则跳过
            visited[cur] = true;  // 标记为已访问
            ans += dist[cur];  // 累加总权值

            for (int i = 0; i < n; i++) {
                if (!visited[i] && graph[cur][i] != 0 && graph[cur][i] < dist[i]) {  // 如果未访问过且有连接，并且距离更近，则更新距离并加入最小堆
                    dist[i] = graph[cur][i];
                    pq.offer(i);
                }
            }
        }
        return ans;
    }

    public static void main(String[] args) {
        int[][] graph = new int[][]{
                {0, 7, 0, 5, 0, 0},
                {7, 0, 8, 9, 7, 0},
                {0, 8, 0, 0, 5, 0},
                {5, 9, 0, 0, 15, 6},
                {0, 7, 5, 15, 0, 8},
                {0, 0, 0, 6, 8, 0}
        };
        System.out.println(prim(graph, graph.length)); // 输出最小生成树的总权值
    }
}