最小生成树问题（Kruskal算法）的优化版本：使用路径压缩与按秩合并的并查集

题目描述

给定一个无向连通图 \(G = (V, E)\)，其中 \(V\) 是顶点集，\(E\) 是边集。每条边 \(e \in E\) 有一个权重 \(w(e)\)。我们需要找到图 \(G\) 的一棵最小生成树（MST），即一个包含所有顶点且边的总权重最小的树。

Kruskal算法是一种经典的最小生成树算法。其基本思想是：按边的权重从小到大排序，然后依次尝试将边加入生成树中，如果加入该边不会形成环，则将其加入，否则跳过。 判断是否形成环需要使用并查集（Union-Find）数据结构。

在基础的Kruskal算法中，通常使用简单的并查集实现，其查找（Find）和合并（Union）操作的最坏时间复杂度为 \(O(n)\) 每次操作（其中 \(n = |V|\)），导致总复杂度为 \(O(m \log m + m n)\)（\(m = |E|\)），在稀疏图中接近 \(O(m n)\)。通过引入路径压缩和按秩合并两种优化，可以将每次查找和合并的平均时间复杂度降低到近乎常数（反阿克曼函数 \(\alpha(n)\)），从而使Kruskal算法的总复杂度优化到 \(O(m \log m)\)，这主要由排序边的时间复杂度决定。

解题过程

我们逐步讲解如何使用带路径压缩和按秩合并的并查集来优化Kruskal算法。

步骤1：理解基础Kruskal算法框架

1. 将图中所有边按权重从小到大排序。
2. 初始化一个空的边集合 \(T\) 用于存放最小生成树的边。
3. 初始化一个并查集，使得每个顶点自成一个集合。
4. 按排序后的顺序遍历每条边 \((u, v, w)\)：
   a. 使用并查集的 Find 操作检查顶点 \(u\) 和 \(v\) 是否属于同一个集合（即是否已连通）。
   b. 如果不在同一个集合（即加入该边不会形成环），则：
   • 将边 \((u, v, w)\) 加入 \(T\)。
   • 使用并查集的 Union 操作将 \(u\) 和 \(v\) 所在的集合合并。
5. 当 \(T\) 中包含 \(n-1\) 条边时，算法终止，\(T\) 即为最小生成树。

步骤2：并查集（Union-Find）数据结构

并查集是一种用于管理元素分组的数据结构，主要支持两种操作：

• Find(x)：查找元素 \(x\) 所在集合的代表元素（通常称为“根”）。
• Union(x, y)：合并元素 \(x\) 和 \(y\) 所在的集合。

在Kruskal算法中，每个集合代表当前生成树森林中的一个连通分量。

步骤3：基础并查集的实现与问题

最简单的实现是使用一个数组 parent，其中 parent[i] 存储顶点 \(i\) 的父节点。初始时，parent[i] = i。

• Find(x)：通过不断访问 parent[x] 直到 parent[x] = x，找到根节点。
• Union(x, y)：将 Find(x) 的根节点的父节点设置为 Find(y) 的根节点。

这种实现在最坏情况下（例如形成一条长链），Find 操作需要 \(O(n)\) 时间。

步骤4：优化1 - 路径压缩（Path Compression）

路径压缩在 Find 操作中进行。当我们找到元素 \(x\) 的根节点 root 后，我们将从 \(x\) 到 root 路径上的所有节点的父节点都直接设置为 root。这样，后续对这条路径上节点的 Find 操作就会非常快。

伪代码：

function Find(x):
    if parent[x] != x:
        parent[x] = Find(parent[x])  // 递归查找并压缩路径
    return parent[x]

通过递归，在返回过程中将路径上所有节点的父节点更新为根节点。

步骤5：优化2 - 按秩合并（Union by Rank）

“秩”（rank）是每个集合树高度的上界。我们维护一个数组 rank，初始时每个顶点的秩为0。

在 Union(x, y) 时：

1. 找到 \(x\) 的根 rootX 和 \(y\) 的根 rootY。
2. 如果 rootX == rootY，它们已在同一集合，直接返回。
3. 比较 rank[rootX] 和 rank[rootY]：
   a. 如果 rank[rootX] < rank[rootY]，则将 parent[rootX] 设置为 rootY。
   b. 如果 rank[rootX] > rank[rootY]，则将 parent[rootY] 设置为 rootX。
   c. 如果相等，则任意将其中一个根作为父节点，并将新根的秩加1。

这样做的目的是保持树的平衡，避免形成过深的树，从而保证操作的高效性。

步骤6：优化后的并查集操作代码示例

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # 路径压缩
        return self.parent[x]

    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX == rootY:
            return False
        # 按秩合并
        if self.rank[rootX] < self.rank[rootY]:
            self.parent[rootX] = rootY
        elif self.rank[rootX] > self.rank[rootY]:
            self.parent[rootY] = rootX
        else:
            self.parent[rootY] = rootX
            self.rank[rootX] += 1
        return True

步骤7：整合优化后的并查集到Kruskal算法

现在，我们将优化后的UnionFind类应用到Kruskal算法的主流程中。

def kruskal_mst(n, edges):
    """
    n: 顶点数量
    edges: 边列表，每个元素为 (u, v, w)，u和v是顶点索引（0-based），w是权重
    """
    # 1. 按边权重排序
    edges.sort(key=lambda x: x[2])
    
    uf = UnionFind(n)
    mst_edges = []
    total_weight = 0
    
    for u, v, w in edges:
        # 2. 检查是否形成环
        if uf.union(u, v):  # 如果不在同一集合，union会合并并返回True
            mst_edges.append((u, v, w))
            total_weight += w
            if len(mst_edges) == n - 1:
                break  # 已找到n-1条边，MST构建完成
    
    if len(mst_edges) != n - 1:
        return None, None  # 图不连通，无法形成MST
    return mst_edges, total_weight

步骤8：复杂度分析

1. 排序：对 \(m\) 条边排序，时间复杂度为 \(O(m \log m)\)。
2. 并查集操作：总共进行 \(O(m)\) 次 Find 和 \(O(n)\) 次 Union（最多 \(n-1\) 次合并成功）。在路径压缩和按秩合并优化下，每次操作的平均时间复杂度为 \(O(\alpha(n))\)，其中 \(\alpha(n)\) 是增长极其缓慢的反阿克曼函数（对于所有实际应用，\(\alpha(n) < 5\)）。因此，并查集部分的总时间可视为 \(O(m \cdot \alpha(n))\)。

总时间复杂度：\(O(m \log m)\)，在稀疏图（\(m = O(n)\)）中为 \(O(n \log n)\)，在稠密图（\(m = O(n^2)\)）中为 \(O(n^2 \log n)\)。
空间复杂度：\(O(n)\) 用于并查集，\(O(m)\) 用于存储边（如果需要存储所有边）。

步骤9：示例验证

考虑一个简单图：
顶点：4个（0, 1, 2, 3）
边：
(0,1,10)
(0,2,6)
(0,3,5)
(1,3,15)
(2,3,4)

执行过程：

1. 边排序后：(2,3,4), (0,3,5), (0,2,6), (0,1,10), (1,3,15)
2. 选取(2,3,4)，合并2和3。
3. 选取(0,3,5)，合并0和3（注意3的根是2，实际合并0和2）。
4. 选取(0,2,6)：此时0和2已在同一集合（通过3连通），跳过。
5. 选取(0,1,10)，合并0和1。
   此时已选取3条边（n-1=3），MST构建完成。总权重=4+5+10=19。

总结

通过结合路径压缩和按秩合并优化并查集，Kruskal算法的效率得到了显著提升，使其成为一种在实践中非常高效和常用的最小生成树算法。其思想直观，实现相对简单，且在处理稀疏图时尤为高效。