xxx 最小生成树的Kruskal算法 题目描述 给定一个连通无向图 G=(V, E)，其中 V 是顶点集，E 是边集，每条边有一个权重（表示距离、成本等）。要求找出一个边的子集 T ⊆ E，使得这些边连接所有顶点且不形成环，并且所有边的权重之和最小。这样的子集 T 称为图 G 的最小生成树（Minimum Spanning Tree, MST）。 解题过程 Kruskal算法采用贪心策略，核心思想是：按边权重从小到大排序，依次选择边，若该边加入后不会与已选边形成环，则加入最小生成树，否则跳过。算法保证最终选出 n-1 条边（n 为顶点数）。 步骤详解 初始化 创建空集合 T 用于存储最小生成树的边。 将图 G 的所有边按权重升序排序。 处理每条边 按排序后的顺序遍历每条边 (u, v)： 检查环 ：判断 u 和 v 是否已在同一连通分量中（即是否已通过已选边间接连通）。若不在同一分量，加入边 (u, v) 不会形成环，执行下一步；否则跳过。 合并连通分量 ：将边 (u, v) 加入 T，并合并 u 和 v 所在的连通分量。 终止条件 当 T 中包含 n-1 条边时停止（n 为顶点数），此时 T 即为最小生成树。 关键工具：并查集（Disjoint Set Union, DSU） 高效实现连通分量检查与合并： 查找（Find） ：确定元素所属的集合代表元。 合并（Union） ：将两个集合合并为一个。 优化方法： 路径压缩 ：在 Find 操作中 flatten 树结构，加速后续查找。 按秩合并 ：Union 时将小树合并到大树下，控制树高度。 实例演示 考虑顶点集 {A, B, C, D}，边权重为： (A-B, 1), (A-C, 3), (A-D, 4), (B-C, 2), (C-D, 5) 排序边：(A-B,1), (B-C,2), (A-C,3), (A-D,4), (C-D,5) 选 (A-B,1)：加入 T，连通分量 {A,B}, {C}, {D} 选 (B-C,2)：加入 T，连通分量 {A,B,C}, {D} 选 (A-C,3)：A,C 已连通（同属 {A,B,C}），跳过 选 (A-D,4)：加入 T，连通分量 {A,B,C,D}，T 已含 3 条边（n=4），停止。 最小生成树权重和为 1+2+4=7。 复杂度分析 排序边：O(|E|log|E|) 并查集操作（优化后）：近似 O(α(|V|))，α 为反阿克曼函数。 总复杂度：O(|E|log|E|)，适用于稀疏图（|E| ≪ |V|²）。