第 46 课 - Kruskal 最小生成树

学习目标

理解最小生成树（MST）的概念及其在实际场景中的应用价值
掌握 Kruskal 算法的贪心策略和实现流程
熟悉并查集（Union-Find）数据结构在 Kruskal 算法中的关键作用
能够使用 Kruskal 算法解决带权无向图的最小生成树问题
了解 Kruskal 算法的时间复杂度及其适用场景

核心概念

什么是最小生成树？

最小生成树是连接图中所有顶点的边的子集，需要满足：

包含图中所有顶点
边的权重之和最小
没有环路（是一棵树）

想象你是一个建筑师，需要连接几个村庄修建公路，要求总造价最低。Kruskal 算法就像一个精明的承包商：始终选择当前最便宜的路，只要这条新路不会形成环路。

Kruskal 算法的核心思想

Kruskal 算法采用贪心策略：

将图中所有边按权重从小到大排序
依次考虑每条边，如果这条边连接的两个顶点不在同一个连通分量中，则选择这条边
重复第 2 步，直到选择了 n-1 条边（n 为顶点数）

关键问题：如何高效判断两个顶点是否在同一连通分量？答案是并查集数据结构。

并查集在 Kruskal 中的作用

并查集用于高效管理顶点所属的连通分量：

find(x): 确定元素 x 属于哪个集合（通常通过返回根节点标识）
union(x, y): 合并两个元素所在的集合

在 Kruskal 算法中，每个顶点初始时自成一个集合。当我们考虑一条边 (u, v) 时：

如果 find(u) != find(v)，说明 u 和 v 在不同的连通分量中
选择这条边后，执行 union(u, v) 将两个连通分量合并

代码示例

class UnionFind:
    """并查集实现，用于高效管理连通分量"""
    def __init__(self, n):
        # 初始化：每个节点都是自己的父节点（独立集合）
        self.parent = list(range(n))
        # rank 用于优化合并操作，按秩合并
        self.rank = [0] * n
    
    def find(self, x):
        """查找 x 的根节点（带路径压缩）"""
        if self.parent[x] != x:
            # 路径压缩：让每个节点直接指向根节点
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        """合并 x 和 y 所在的集合（按秩合并）"""
        root_x = self.find(x)
        root_y = self.find(y)
        
        # 如果已经在同一集合中，无需合并
        if root_x == root_y:
            return False
        
        # 按秩合并：将秩小的树连接到秩大的树上
        if self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
        elif self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
        else:
            # 秩相等时，选择其中一个作为新根，并增加秩
            self.parent[root_y] = root_x
            self.rank[root_x] += 1
        
        return True


def kruskal_mst(vertices, edges):
    """
    Kruskal 算法求解最小生成树
    
    参数:
        vertices: 顶点数量
        edges: 边的列表，格式为 [(权重, 起点, 终点), ...]
    
    返回:
        mst_edges: 最小生成树的边列表
        total_weight: 最小生成树的总权重
    """
    # 1. 按权重排序所有边（升序）
    sorted_edges = sorted(edges, key=lambda x: x[0])
    
    # 2. 初始化并查集
    uf = UnionFind(vertices)
    
    mst_edges = []
    total_weight = 0
    
    # 3. 按顺序考虑每条边
    for weight, u, v in sorted_edges:
        # 检查这条边是否会导致环路
        if uf.find(u) != uf.find(v):
            # 选择这条边
            mst_edges.append((u, v, weight))
            total_weight += weight
            
            # 合并两个连通分量
            uf.union(u, v)
            
            # 如果已经选择了 n-1 条边，提前结束
            if len(mst_edges) == vertices - 1:
                break
    
    return mst_edges, total_weight


# 测试示例
def main():
    # 创建一个示例图
    # 顶点: 0, 1, 2, 3, 4
    vertices = 5
    
    # 边: (权重, 起点, 终点)
    edges = [
        (2, 0, 1),  # 边 0-1，权重 2
        (3, 0, 4),  # 边 0-4，权重 3
        (5, 1, 4),  # 边 1-4，权重 5
        (1, 1, 2),  # 边 1-2，权重 1
        (4, 2, 4),  # 边 2-4，权重 4
        (6, 2, 3),  # 边 2-3，权重 6
        (7, 3, 4),  # 边 3-4，权重 7
    ]
    
    print("=== Kruskal 最小生成树算法演示 ===")
    print(f"输入图有 {vertices} 个顶点，{len(edges)} 条边")
    
    # 运行 Kruskal 算法
    mst_edges, total_weight = kruskal_mst(vertices, edges)
    
    print("\n=== 结果 ===")
    print("最小生成树包含以下边:")
    for u, v, weight in mst_edges:
        print(f"边 {u} -- {v}, 权重: {weight}")
    
    print(f"\n最小生成树总权重: {total_weight}")
    print(f"共选择了 {len(mst_edges)} 条边")


if __name__ == "__main__":
    main()

实践练习

练习 1：基础理解

要求：考虑下图的边列表：[(1, A, B), (3, A, C), (2, B, C), (4, B, D), (5, C, D)]

请手动模拟 Kruskal 算法的执行过程
写出选择边的顺序
计算最小生成树的总权重

预期输出：

选择顺序: (1, A, B), (2, B, C), (4, B, D)
总权重: 7

练习 2：代码实现

要求：扩展上述代码，添加一个 visualize_mst() 函数，使用简单的文本方式显示图和最小生成树。

提示：

创建一个函数，接受原始边列表和 MST 边列表
为所有边显示标记，属于 MST 的边用特殊符号标识
按顶点对展示连接关系

练习 3：实际应用

要求：假设你有 6 个无线网络节点，它们之间的信号强度（权重越小越好）如下：

edges = [
    (10, 0, 1), (15, 0, 2), (20, 1, 2),
    (25, 1, 3), (30, 2, 4), (35, 3, 4),
    (40, 3, 5), (45, 4, 5), (50, 1, 4)
]

使用 Kruskal 算法找到连接所有节点的最优网络拓扑，输出选择的连接和总信号强度。

常见错误

1. 忽略并查集的路径压缩

# 错误写法 - 没有路径压缩
def find(self, x):
    if self.parent[x] != x:
        return self.find(self.parent[x])  # 递归但未压缩
    return x

# 正确写法 - 带路径压缩
def find(self, x):
    if self.parent[x] != x:
        self.parent[x] = self.find(self.parent[x])  # 压缩路径
    return self.parent[x]

2. 边排序不彻底

Kruskal 算法要求严格按权重升序排序，如果权重相等，边的顺序可能影响结果，但不影响正确性。

3. 过早终止循环

一些初学者会在选择了 n-1 条边后立即停止，但忘记检查是否所有顶点都已连通。对于非连通图，最小生成树不存在。

4. 忽略图的连通性

如果图本身不连通，Kruskal 算法会生成最小生成森林（每个连通分量的最小生成树）。需要在算法开始时检查或明确处理这种情况。

5. 并查集合并逻辑错误

# 错误：总是把 y 合并到 x
def union(self, x, y):
    self.parent[find(y)] = find(x)  # 可能导致树过深

# 正确：按秩合并
def union(self, x, y):
    root_x = self.find(x)
    root_y = self.find(y)
    if self.rank[root_x] < self.rank[root_y]:
        self.parent[root_x] = root_y
    else:
        self.parent[root_y] = root_x
        if self.rank[root_x] == self.rank[root_y]:
            self.rank[root_x] += 1

小结

关键要点回顾

Kruskal 算法本质：基于贪心策略，逐步选择不会形成环路的最小权重边
并查集是关键：高效管理连通分量，判断新边是否会导致环路
时间复杂度：
- 主要时间消耗在边的排序：O(E log E)
- 并查集操作：几乎 O(α(V))，α 是反阿克曼函数，实际可视为常数
- 总复杂度：O(E log E)，适合边稀疏的图
适用场景：
- 边稀疏的图（E 相对较小）
- 边已经部分排序的图
- 需要在线处理边流的情况（可稍作修改）
与 Prim 算法对比：
- Kruskal：全局考虑所有边，适合稀疏图
- Prim：逐步扩展顶点集合，适合稠密图

思考题

如果图中所有边的权重都相等，Kruskal 算法会返回什么？
如何修改 Kruskal 算法来找到最大生成树？
在什么情况下，Kruskal 算法会失败（找不到生成树）？

下一步学习

下一课我们将学习另一种最小生成树算法——Prim 算法，它采用不同的贪心策略（从顶点出发逐步扩展），并与 Kruskal 算法进行对比分析。理解这两种算法的区别和适用场景，将帮助你在实际问题中选择最合适的解决方案。

练习编辑器

rust