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

Kruskal 算法也是一种得到最小生成树的算法。它会从所有边中选取权重最小的边,若该边的两个节点不在同一个连通分量中,则选取该边加入到最小生成树中。
我们可以使用并查集和优先队列实现 Kruskal 算法:

public List<Edge> kruskalMST(List<Edge> edges) {
    int n = edges.size();
    DisjointSet ds = new DisjointSet(n);   // 并查集

    PriorityQueue<Edge> pq = new PriorityQueue<>(edges); // 小顶堆根据边的权重排序

    List<Edge> res = new ArrayList<>();      // 结果列表

    while (!pq.isEmpty()) {
        Edge e = pq.poll();     // 取出队列中权重最小的边

        int root1 = ds.find(e.from);
        int root2 = ds.find(e.to);

        if (root1 != root2) {   // 如果两个节点不在同一连通分量中
            res.add(e);       // 添加该边到结果
            ds.union(root1, root2);   // 合并两个节点所在的连通分量
        }
    }

    return res;
}

算法流程:

1. 初始化并查集ds和小顶堆pq。
2. 从pq中弹出权重最小的边e。
3. 获取e的两个节点所在的连通分量根节点root1和root2。
4. 如果root1 != root2,说明这两个节点不在同一连通分量中。则将e添加到结果,并合并两个连通分量。
5. 重复步骤2-4,直到pq为空。得到的所有边构成最小生成树。
6. 返回结果列表,得到最小生成树的所有边。

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

所以,Kruskal 算法的关键是:

1. 使用优先队列找出权重最小的边。
2. 使用并查集判断该边的两个节点是否在同一连通分量中。
3. 如果不在同一连通分量中,则添加该边到结果,并合并两个连通分量。
4. 重复此过程直到优先队列为空,得到最小生成树的所有边。