最小生成树的 Kruskal 算法
字数 2155 2025-12-14 14:07:08

最小生成树的 Kruskal 算法

题目描述
给定一个无向连通图 \(G = (V, E)\)，其中 \(V\) 是顶点集，\(E\) 是边集，每条边 \(e \in E\) 有一个权重 \(w(e)\)。目标是找出图 \(G\) 的一棵最小生成树（MST），即一个包含 \(G\) 的所有顶点的无环连通子图，使得所有边的权重之和最小。Kruskal 算法是一种基于贪心策略的经典算法，它通过按权重升序依次考虑边，并避免形成环，来逐步构建最小生成树。

解题过程

Kruskal 算法的核心思想是：从小到大考虑边，如果加入当前边不会形成环，就将其加入生成树；否则跳过。 这个过程持续到生成树包含 \(|V| - 1\) 条边（因为一棵树有 \(|V|\) 个顶点时，边数为 \(|V| - 1\)）。

步骤 1：数据准备

  1. 将图 \(G\) 的所有边按权重从小到大排序。排序是为了确保贪心策略：每次考虑当前最小的边。
  2. 准备一个并查集（Disjoint Set Union, DSU）数据结构，用于管理顶点的连通分量。初始时，每个顶点自成一个集合（即每个顶点是独立的连通分量）。并查集支持两种操作：
    • Find(u)：查找顶点 \(u\) 所在集合的代表元素（根节点）。
    • Union(u, v)：合并顶点 \(u\) 和 \(v\) 所在的集合。

步骤 2：边的处理

  1. 初始化一个空集合 \(T\)，用于存储最小生成树的边。
  2. 按权重升序遍历每条边 \((u, v, w)\)：
    • 使用并查集检查 \(u\) 和 \(v\) 是否在同一个集合中（即调用 Find(u) 和 Find(v)，比较它们的根节点是否相同）。
      • 如果不在同一个集合，说明加入边 \((u, v)\) 不会形成环。此时：
        1. 将边 \((u, v, w)\) 加入 \(T\)。
        2. 调用 Union(u, v) 合并 \(u\) 和 \(v\) 所在的集合，表示它们现在连通了。
      • 如果在同一个集合，说明 \(u\) 和 \(v\) 已经连通，加入这条边会形成环，因此跳过。
  3. 当 \(T\) 中包含 \(|V| - 1\) 条边时，算法终止，此时 \(T\) 就是最小生成树的所有边。

步骤 3：正确性保证
Kruskal 算法的正确性基于贪心选择性质和并查集的高效环检测：

  • 贪心选择性质：全局最小生成树一定包含当前未考虑边中权重最小且不会形成环的边。Kruskal 算法正是通过排序和避免环来满足这一性质。
  • 环检测：如果边 \((u, v)\) 的两个端点已连通，加入它会形成环，因此舍弃。并查集可以在接近常数时间内完成查询和合并操作，使算法高效。

步骤 4：复杂度分析

  • 排序边：\(O(|E| \log |E|)\)。由于 \(|E| \leq |V|^2\)，也可写作 \(O(|E| \log |V|)\)。
  • 并查集操作：对于每条边，进行最多两次 Find 和可能的 Union。使用路径压缩和按秩优化的并查集，每次操作的平均时间接近 \(O(\alpha(|V|))\)，其中 \(\alpha\) 是阿克曼函数的反函数，可视为常数。总复杂度为 \(O(|E| \cdot \alpha(|V|))\)。
  • 总体时间复杂度：\(O(|E| \log |V|)\)，主要由排序决定。空间复杂度为 \(O(|V| + |E|)\) 用于存储图和并查集。

举例说明
考虑一个简单无向图，顶点集 \(V = \{A, B, C, D\}\)，边集和权重如下：

  • (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)。

  1. 初始：并查集中每个顶点独立，\(T = \{\}\)。
  2. 处理 (A, B, 1)：A 和 B 不在同一集合，加入 T，合并 {A, B}。T = {(A, B, 1)}。
  3. 处理 (B, C, 2)：B 在 {A, B}，C 在 {C}，不同集合，加入 T，合并 {A, B, C}。T = {(A, B, 1), (B, C, 2)}。
  4. 处理 (A, C, 3)：A 和 C 都在 {A, B, C}，同一集合，跳过（避免环）。
  5. 处理 (B, D, 4)：B 在 {A, B, C}，D 在 {D}，不同集合，加入 T，合并 {A, B, C, D}。此时 T 有 3 条边，满足 |V| - 1 = 3，算法终止。

最小生成树为 {(A, B, 1), (B, C, 2), (B, D, 4)}，总权重为 7。

关键点总结

  • Kruskal 算法适用于稀疏图（边数较少），因为其时间主要受排序影响。
  • 并查集是高效实现的关键，它快速判断连通性并合并分量。
  • 算法保证找到全局最优解，前提是图是连通的。如果图不连通，算法会找到最小生成森林（每个连通分量的最小生成树）。
最小生成树的 Kruskal 算法 题目描述 给定一个无向连通图 \( G = (V, E) \)，其中 \( V \) 是顶点集，\( E \) 是边集，每条边 \( e \in E \) 有一个权重 \( w(e) \)。目标是找出图 \( G \) 的一棵最小生成树（MST），即一个包含 \( G \) 的所有顶点的无环连通子图，使得所有边的权重之和最小。Kruskal 算法是一种基于贪心策略的经典算法，它通过按权重升序依次考虑边，并避免形成环，来逐步构建最小生成树。 解题过程 Kruskal 算法的核心思想是： 从小到大考虑边，如果加入当前边不会形成环，就将其加入生成树；否则跳过。 这个过程持续到生成树包含 \( |V| - 1 \) 条边（因为一棵树有 \( |V| \) 个顶点时，边数为 \( |V| - 1 \)）。 步骤 1：数据准备 将图 \( G \) 的所有边按权重从小到大排序。排序是为了确保贪心策略：每次考虑当前最小的边。 准备一个 并查集 （Disjoint Set Union, DSU）数据结构，用于管理顶点的连通分量。初始时，每个顶点自成一个集合（即每个顶点是独立的连通分量）。并查集支持两种操作： Find(u) ：查找顶点 \( u \) 所在集合的代表元素（根节点）。 Union(u, v) ：合并顶点 \( u \) 和 \( v \) 所在的集合。 步骤 2：边的处理 初始化一个空集合 \( T \)，用于存储最小生成树的边。 按权重升序遍历每条边 \( (u, v, w) \)： 使用并查集检查 \( u \) 和 \( v \) 是否在同一个集合中（即调用 Find(u) 和 Find(v) ，比较它们的根节点是否相同）。 如果 不在同一个集合 ，说明加入边 \( (u, v) \) 不会形成环。此时： 将边 \( (u, v, w) \) 加入 \( T \)。 调用 Union(u, v) 合并 \( u \) 和 \( v \) 所在的集合，表示它们现在连通了。 如果 在同一个集合 ，说明 \( u \) 和 \( v \) 已经连通，加入这条边会形成环，因此跳过。 当 \( T \) 中包含 \( |V| - 1 \) 条边时，算法终止，此时 \( T \) 就是最小生成树的所有边。 步骤 3：正确性保证 Kruskal 算法的正确性基于贪心选择性质和并查集的高效环检测： 贪心选择性质 ：全局最小生成树一定包含当前未考虑边中权重最小且不会形成环的边。Kruskal 算法正是通过排序和避免环来满足这一性质。 环检测 ：如果边 \( (u, v) \) 的两个端点已连通，加入它会形成环，因此舍弃。并查集可以在接近常数时间内完成查询和合并操作，使算法高效。 步骤 4：复杂度分析 排序边：\( O(|E| \log |E|) \)。由于 \( |E| \leq |V|^2 \)，也可写作 \( O(|E| \log |V|) \)。 并查集操作：对于每条边，进行最多两次 Find 和可能的 Union 。使用路径压缩和按秩优化的并查集，每次操作的平均时间接近 \( O(\alpha(|V|)) \)，其中 \( \alpha \) 是阿克曼函数的反函数，可视为常数。总复杂度为 \( O(|E| \cdot \alpha(|V|)) \)。 总体时间复杂度： \( O(|E| \log |V|) \) ，主要由排序决定。空间复杂度为 \( O(|V| + |E|) \) 用于存储图和并查集。 举例说明 考虑一个简单无向图，顶点集 \( V = \{A, B, C, D\} \)，边集和权重如下： (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)。 初始：并查集中每个顶点独立，\( T = \{\} \)。 处理 (A, B, 1)：A 和 B 不在同一集合，加入 T，合并 {A, B}。T = {(A, B, 1)}。 处理 (B, C, 2)：B 在 {A, B}，C 在 {C}，不同集合，加入 T，合并 {A, B, C}。T = {(A, B, 1), (B, C, 2)}。 处理 (A, C, 3)：A 和 C 都在 {A, B, C}，同一集合，跳过（避免环）。 处理 (B, D, 4)：B 在 {A, B, C}，D 在 {D}，不同集合，加入 T，合并 {A, B, C, D}。此时 T 有 3 条边，满足 |V| - 1 = 3，算法终止。 最小生成树为 {(A, B, 1), (B, C, 2), (B, D, 4)}，总权重为 7。 关键点总结 Kruskal 算法适用于稀疏图（边数较少），因为其时间主要受排序影响。 并查集是高效实现的关键，它快速判断连通性并合并分量。 算法保证找到全局最优解，前提是图是连通的。如果图不连通，算法会找到最小生成森林（每个连通分量的最小生成树）。