排序后顺序不变（权重已升序）。

xxx 最小生成树的 Kruskal 算法 题目描述 给定一个无向连通图 \( G = (V, E) \)，其中每条边 \( e \) 有一个权重 \( w(e) \)，要求找到图 \( G \) 的最小生成树（Minimum Spanning Tree, MST）。最小生成树是原图的一个子图，它是一棵树，包含原图所有顶点，且边的权重之和最小。Kruskal 算法通过贪心策略，按边权重从小到大逐步选择边来构建最小生成树。 解题过程 算法思想 Kruskal 算法的核心思想是： 将图中所有边按权重从小到大排序。 从权重最小的边开始，依次考虑每条边，如果加入该边不会形成环，则将其加入最小生成树；否则跳过。 直到最小生成树中包含 \( |V| - 1 \) 条边为止。 关键步骤 排序边 ：将边集 \( E \) 按权重非降序排序。 初始化并查集 ：为每个顶点初始化一个集合（用于检测环）。 遍历边并检查环 ：对于每条边 \( (u, v) \)，检查 \( u \) 和 \( v \) 是否属于同一集合（即是否连通）。若不属于同一集合，则加入该边，并合并两个集合。 终止条件 ：当已选边数达到 \( |V| - 1 \) 时结束。 详细步骤 步骤 1：排序边 将边按权重升序排列，例如： \[ \text{边集} = [ (1,2,1), (2,3,2), (1,3,3) ] \] 排序后顺序不变（权重已升序）。 步骤 2：初始化并查集 为每个顶点创建独立集合： \[ \{1\}, \{2\}, \{3\} \] 步骤 3：遍历边并构建 MST 取边 \( (1,2) \)（权重 1）：顶点 1 和 2 不在同一集合，加入 MST，合并集合为 \( \{1,2\}, \{3\} \)。 取边 \( (2,3) \)（权重 2）：顶点 2 和 3 不在同一集合，加入 MST，合并集合为 \( \{1,2,3\} \)。 取边 \( (1,3) \)（权重 3）：顶点 1 和 3 在同一集合（会形成环），跳过。 已选边数达到 \( |V|-1 = 2 \)，终止。 算法正确性说明 Kruskal 算法是贪心算法，每次选择当前最小权重且不形成环的边。 通过并查集高效检测连通性，确保无环。 正确性基于贪心选择性质和最小生成树的割性质。 时间复杂度分析 排序边：\( O(|E| \log |E|) \)。 并查集操作（路径压缩 + 按秩合并）：近似 \( O(\alpha(|V|)) \) 每次操作，总复杂度 \( O(|E| \alpha(|V|)) \)。 总复杂度：\( O(|E| \log |E|) \)。 总结 Kruskal 算法通过贪心选择权重最小的边，并利用并查集避免环的形成，高效构建最小生成树。适用于稀疏图（边数较少的情况），因其复杂度主要由排序边决定。