Kruskal算法（最小生成树） 描述 Kruskal算法是一种用于在加权无向连通图中寻找最小生成树（MST）的贪心算法。最小生成树是原图的一个子图，它包含所有顶点，且是一棵树（无环连通），同时其所有边的权重之和最小。Kruskal算法的核心思想是：按权重从小到大依次选择边，如果加入该边不会形成环，则将其加入生成树；否则跳过。该算法适用于稀疏图（边数相对较少），通常使用并查集（Union-Find）数据结构来高效判断环的存在。 解题过程 假设有一个加权无向图，顶点集为{V}，边集为{E}，每条边有权重。目标是构建一棵最小生成树。 步骤1: 边按权重排序 首先，将图中所有边按权重从小到大排序。例如，若边权重为[ 5, 1, 3, 2]，排序后为[ 1, 2, 3, 5 ]。这一步确保算法优先考虑权重小的边，符合贪心策略。 步骤2: 初始化并查集 创建一个并查集（Union-Find）数据结构，用于管理顶点的连通分量。初始时，每个顶点自成一个集合（即每个顶点的根节点是自身）。并查集提供两种操作： find(x) ：查找顶点x所在集合的代表（根节点），用于判断两个顶点是否属于同一集合。 union(x, y) ：合并顶点x和y所在的集合，用于连接两个连通分量。 同时，初始化一个空集合MST（或列表），用于存储最小生成树的边。 步骤3: 遍历边并判断环 按排序后的顺序遍历每条边(u, v, weight)： 使用并查集的 find(u) 和 find(v) 操作，检查u和v的根节点是否相同： 如果根节点不同 ：说明u和v不在同一连通分量中，加入边(u, v)不会形成环。执行以下操作： 将边(u, v, weight)加入MST集合。 调用 union(u, v) 合并u和v所在的集合，使它们属于同一连通分量。 如果根节点相同 ：说明u和v已在同一连通分量中，加入边(u, v)会形成环，因此跳过该边。 重复此过程，直到MST中包含|V| - 1条边（因为一棵树的边数总比顶点数少1）。 步骤4: 算法终止与结果 当MST的边数达到|V| - 1时，算法终止。此时MST即为最小生成树，包含所有顶点且总权重最小。 如果遍历完所有边后，MST的边数仍不足|V| - 1，说明原图不连通，不存在最小生成树（但题目通常假设图是连通的）。 举例说明 假设图有4个顶点{A, B, C, D}，边和权重为： (A, B, 1) (B, C, 2) (C, D, 3) (A, D, 4) (B, D, 5) 排序边 ：按权重排序后顺序为[ (A,B,1), (B,C,2), (C,D,3), (A,D,4), (B,D,5) ]。 初始化 ：并查集中每个顶点自成集合：{A}, {B}, {C}, {D}；MST为空。 处理边 ： 边(A,B,1)：find(A)≠find(B)，加入MST，合并{A,B} → 集合变为{AB}, {C}, {D}。 边(B,C,2)：find(B)≠find(C)，加入MST，合并{AB,C} → 集合变为{ABC}, {D}。 边(C,D,3)：find(C)≠find(D)，加入MST，合并{ABC,D} → 集合变为{ABCD}。 此时MST已有3条边（|V|=4，边数已够），算法终止。 结果 ：MST包含边[ (A,B,1), (B,C,2), (C,D,3) ]，总权重为6。 关键点 贪心选择 ：每次选最小权重边，保证局部最优导向全局最优。 环检测 ：通过并查集高效判断连通性，时间复杂度接近O(1)。 时间复杂度 ：排序边需O(E log E)，并查集操作约O(E α(V))（α为反阿克曼函数，增长极慢），总体以排序为主，即O(E log E)。