如何实现Prim最小生成树算法？

Prim 算法是一种用于寻找权重最小的生成树的算法。它会从某个节点开始,逐步添加与该节点直接相连且权值最小的节点,直到所有节点都被添加到生成树中。

我们可以使用优先队列实现 Prim 算法:

public List<Edge> primMST(List<Edge>[] graph) {
    int n = graph.length;
    boolean[] visited = new boolean[n];
    PriorityQueue<Edge> pq = new PriorityQueue<>((a, b) -> a.weight - b.weight);

    pq.offer(new Edge(0, 1, graph[0].get(1).weight));  // 起始边 (0, 1) 入队列
    List<Edge> res = new ArrayList<>();
    visited[0] = true;     // 标记节点 0 为已访问

    while (!pq.isEmpty()) {
        Edge e = pq.poll();     // 取出权重最小的边
        if (visited[e.to]) continue;   // 如果e的终点节点已被访问则跳过

        res.add(e);         // 添加当前边到结果
        visited[e.to] = true;       // 标记e的终点节点为已访问     

        for (Edge edge : graph[e.to]) {   // 遍历e的终点节点相邻的所有边
            if (!visited[edge.to]) pq.offer(edge);   // 如果边的终点未被访问则入队列
        }
    }

    return res;
}

算法流程:

1. 访问节点 0,将节点 0 相邻的所有边入队列。标记节点 0 为已访问。
2. 从队列中弹出权重最小的边 e。如果 e 的终点节点已被访问则跳过。
3. 将 e 添加到结果,并标记 e 的终点节点为已访问。
4. 将 e 的终点节点相邻的所有未访问边入队列。
5. 重复步骤 2-4,直到队列为空。得到的所有边构成最小生成树。
6. 返回结果,得到最小生成树的所有边。

时间复杂度 O(nlogn),空间复杂度 O(n)。

所以,Prim 算法的关键是:

1. 使用优先队列找出权重最小的边。
2. 如果某条边的终点节点已访问,则跳过这条边。
3. 添加选中的边到结果,并标记相关节点为已访问。
4. 将选中的边的终点相邻的未访问边入队列。
5. 重复此过程直到队列为空,得到最小生成树的所有边。