最小生成树：Kruskal算法 最小生成树（Minimum Spanning Tree, MST）是图论中的一个经典问题，旨在从给定的连通无向图中找出一棵生成树，使得所有边的权重之和最小。Kruskal算法是一种基于贪心策略的算法，用于高效解决最小生成树问题。 问题描述 假设有一个连通无向图 \( G = (V, E) \)，其中 \( V \) 是顶点集合，\( E \) 是边集合，每条边 \( e \in E \) 有一个权重 \( w(e) \)。目标是选择 \( |V| - 1 \) 条边构成一棵树，使得总权重最小。 Kruskal算法的核心思想 Kruskal算法通过不断选择当前未选边中权重最小的边来构建最小生成树，但需确保加入的边不会与已选边形成环。这可以通过并查集（Union-Find）数据结构高效实现。 详细步骤 初始化 ： 将图中的所有边按权重从小到大排序。 创建一个并查集结构，初始时每个顶点自成一个集合（即每个顶点的根节点为自己）。 初始化一个空集合 \( MST \) 用于存储最小生成树的边。 遍历边并检查环 ： 按权重从小到大遍历每条边 \( (u, v) \)： 使用并查集的 Find 操作检查顶点 \( u \) 和 \( v \) 是否属于同一集合（即是否连通）。 若不属于同一集合（即不连通），说明加入边 \( (u, v) \) 不会形成环，则： 将该边加入 \( MST \)。 使用并查集的 Union 操作合并 \( u \) 和 \( v \) 所在的集合。 若属于同一集合，则跳过该边（避免环）。 终止条件 ： 当 \( MST \) 中包含 \( |V| - 1 \) 条边时，算法终止，此时 \( MST \) 即为最小生成树。 示例演示 考虑一个简单图，顶点集 \( V = \{A, B, C, D\} \)，边集 \( E \) 及权重如下： \( (A, B, 1) \) \( (A, C, 3) \) \( (B, C, 2) \) \( (B, D, 4) \) \( (C, D, 5) \) 执行过程 ： 排序边 ：按权重排序后顺序为 \( (A,B,1) \), \( (B,C,2) \), \( (A,C,3) \), \( (B,D,4) \), \( (C,D,5) \)。 初始化并查集 ：每个顶点独立成集合：\{A\}, \{B\}, \{C\}, \{D\}。 处理边 ： 选择 \( (A,B,1) \)：A 和 B 不在同一集合，加入 MST，合并集合为 \{A,B\}, \{C\}, \{D\}。 选择 \( (B,C,2) \)：B 和 C 不在同一集合，加入 MST，合并集合为 \{A,B,C\}, \{D\}。 选择 \( (A,C,3) \)：A 和 C 已在同一集合（因 A-B-C 已连通），跳过。 选择 \( (B,D,4) \)：B 和 D 不在同一集合，加入 MST，合并集合为 \{A,B,C,D\}。 此时 MST 已有 \( |V| - 1 = 3 \) 条边，算法终止。 最终最小生成树包含边 \( (A,B,1) \), \( (B,C,2) \), \( (B,D,4) \)，总权重为 7。 时间复杂度分析 排序边：\( O(|E| \log |E|) \)。 并查集操作：每次 Find 和 Union 操作接近常数时间（使用路径压缩和按秩合并优化），总体约 \( O(|E| \alpha(|V|)) \)，其中 \( \alpha \) 是反阿克曼函数。 总复杂度主要由排序决定，为 \( O(|E| \log |E|) \)。 关键点总结 Kruskal算法是贪心算法的典型应用，通过局部最优选择达到全局最优。 并查集的高效实现是避免环检测的关键，确保算法在稀疏图（\( |E| \ll |V|^2 \)）中高效运行。 适用于边权重易排序且图规模较大的场景，与Prim算法（基于顶点扩展）形成互补。