xxx 最小生成树的Kruskal算法 题目描述 给定一个连通无向图 \( G = (V, E) \)，其中 \( V \) 是顶点集合，\( E \) 是边集合，每条边 \( (u, v) \) 有一个权重 \( w(u, v) \)。要求找到一个边的子集 \( T \subseteq E \)，使得所有顶点通过 \( T \) 连通，并且总权重 \( \sum_ {(u,v) \in T} w(u,v) \) 最小。这样的子集 \( T \) 称为最小生成树（Minimum Spanning Tree, MST）。Kruskal算法通过贪心策略解决该问题。 解题过程 初始化 将边按权重从小到大排序。 创建一个空的集合 \( T \) 用于存储最小生成树的边。 初始化一个并查集（Disjoint Set Union, DSU）数据结构，每个顶点自成一个集合（即初始时每个顶点的根节点为自己）。 遍历边并检查环路 按权重从小到大遍历每条边 \( (u, v) \)： 使用并查集检查 \( u \) 和 \( v \) 是否属于同一集合（即根节点是否相同）。 如果属于不同集合，说明加入 \( (u, v) \) 不会形成环路，则将这条边加入 \( T \)，并在并查集中合并 \( u \) 和 \( v \) 所在的集合。 如果属于同一集合，跳过该边（避免环路）。 重复直到 \( T \) 包含 \( |V| - 1 \) 条边（生成树的边数固定）。 算法终止 当 \( T \) 的边数达到 \( |V| - 1 \) 时，算法结束，\( T \) 即为最小生成树。 关键点说明 贪心策略有效性 ：每次选择权重最小的合法边，能保证全局最优（基于切性质定理）。 并查集的作用 ：高效管理顶点连通性，合并和查询操作的时间复杂度接近常数（路径压缩和按秩优化）。 复杂度 ：排序边需 \( O(|E| \log |E|) \)，并查集操作约 \( O(|E| \alpha(|V|)) \)，总复杂度为 \( O(|E| \log |E|) \)，其中 \( \alpha \) 是反阿克曼函数。 示例 假设图有顶点 \( \{A, B, C, D\} \)，边权重为 \( (A,B)=1, (A,C)=3, (B,C)=2, (C,D)=4 \)。 排序边：\( (A,B), (B,C), (A,C), (C,D) \)。 依次加入 \( (A,B) \)、\( (B,C) \)，跳过 \( (A,C) \)（因为 \( A \) 和 \( C \) 已连通），最后加入 \( (C,D) \)，得到总权重为 7 的 MST。