连通关系回答两点是否已通过若干条边连接。并查集把每个连通分量表示为一棵父指针树：find 找代表元，union 把两棵树合并。它保存的是连通划分，不能直接恢复图上的实际路径，也不负责保存每一条原始边。

让树保持浅

按大小合并，把小树根挂到大树根上，避免总往链尾连接。路径压缩在查找时把经过的节点改指向更靠近根的位置。两者一起使用时，一串操作的摊还成本与反阿克曼函数相关，实际规模下增长极慢；这不是严格的“每次最坏 O(1)”。

本例使用路径折半：沿父指针前进时让当前节点指向祖父。只有根保存有效分量大小，非根的旧大小不能继续当作独立分量大小使用。重复合并同一分量返回False，不应该再次增加大小。

class DisjointSet:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n

    def find(self, node):
        while self.parent[node] != node:
            self.parent[node] = self.parent[self.parent[node]]
            node = self.parent[node]
        return node

    def union(self, a, b):
        a, b = self.find(a), self.find(b)
        if a == b:
            return False
        if self.size[a] < self.size[b]:
            a, b = b, a
        self.parent[b] = a
        self.size[a] += self.size[b]
        return True


def minimum_spanning_forest(n, edges):
    if n < 0 or any(not (0 <= a < n and 0 <= b < n) for _, a, b in edges):
        raise ValueError('invalid vertex')
    sets = DisjointSet(n)
    chosen, cost, components = [], 0, n
    for weight, a, b in sorted(edges):
        if sets.union(a, b):
            chosen.append((weight, a, b))
            cost += weight
            components -= 1
    return cost, chosen, components


if __name__ == '__main__':
    print(minimum_spanning_forest(4, [(2, 0, 1), (1, 1, 2), (4, 0, 2), (3, 2, 3)]))

Kruskal为什么不只是在避免环

最小生成树要用最小总边权连接所有顶点。Kruskal按权重从小到大检查边，若端点属于不同分量就接受并合并。每次接受的边连接两个分量，不会成环。安全性来自割性质：把当前一个分量与其余顶点分开，跨越该割的最轻边可以属于某棵最小生成树。

更具体地，若某个最优解没有这条边，把它加入会形成环；环上存在另一条跨割边，权重不小于当前边，用当前边替换它不会增加总权重。因此每一步都能保留一个与已选边兼容的最优解。

代码对不连通图返回最小生成森林，同时返回最终分量数量。需要生成树时必须检查连通性，不能把少于 V-1 条边的结果悄悄当成生成树。自环不会帮助合并，平行边可以参与比较；负权边本身不妨碍最小生成树，与Dijkstra的条件不同。

排序占 O(E log E)，并查集操作接近线性，空间包括排序后的边列表和 O(V) 状态。Prim则从一个顶点不断扩展已连接集合，也依赖割性质，常用堆选下一条边；图存储方式和稠密程度会影响具体实现。

适用边界

并查集适合边逐步加入的连通性问题。删除一条边可能拆开分量，普通并查集没有足够信息支持这种操作；离线反向处理、可回滚结构或动态连通算法需要另外设计。带路径压缩的结构也不能不加修改地套到简单回滚栈里。

最小生成树最小化总建设成本，单源最短路最小化从一个源点到各点的距离。一个总边权最小的网络，不保证从指定起点走到每个节点都最短。

练习与面试自查

为四五个顶点枚举所有 V-1 条边的子集，筛掉不连通者，与Kruskal总权重比较。再加入孤立点、重复边、负边和自环。检查输出边始终无环，且每个原始连通分量内保持连通。

面试应能说明代表元为什么可以变化、路径压缩改变了什么、最小生成树为什么可以有多个同权答案，以及普通并查集为什么无法直接回答两点间的具体路径。

本地运行

示例仅使用 Python 标准库，适用于 Python 3.10 及以上。把 example.py 与 test_example.py 保存到同一个目录，在该目录运行：

python example.py
python -m unittest -v test_example.py

测试检查本文列出的边界；新增练习仍需自己补充断言。

参考资料