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

最小生成树是连接图中所有节点的最小权重的树。常用的算法有 Prim 算法和 Kruskal 算法。

我们可以使用 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));
    List<Edge> res = new ArrayList<>();
    while (!pq.isEmpty()) {
        Edge e = pq.poll();
        if (visited[e.from] && visited[e.to]) continue;   // 如果两个节点都被访问过则跳过

        res.add(e);     // 添加当前边到结果列表
        visited[e.from] = true;
        visited[e.to] = true;

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

    return res;
} 

算法流程:

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

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

所以,Prim 算法的关键是:

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