最小生成树的 Kruskal 算法
字数 2416 2025-12-10 18:35:34

最小生成树的 Kruskal 算法

题目描述

给定一个连通的无向图 \(G = (V, E)\)，其中 \(V\) 是顶点集合，\(E\) 是边集合。每条边 \(e \in E\) 都有一个权重（或成本） \(w(e)\)。目标是找到一个边的子集 \(T \subseteq E\)，使得 \(T\) 中的边连接所有顶点，并且形成一个树（即无环且连通），同时使 \(T\) 中所有边的权重之和最小。这样的树被称为图 \(G\) 的最小生成树。

Kruskal 算法就是一种经典的贪心算法，用于解决最小生成树问题。它的核心思想是：按边权重从小到大的顺序考虑边，如果加入这条边不会在当前已选的边集中形成环，就将其加入生成树；否则跳过。直到选中了 \(|V| - 1\) 条边为止。

解题过程循序渐进讲解

步骤 1：算法核心思想与准备
Kruskal 算法是一种贪心算法。其正确性基于一个关键性质：对于任意一个割（将顶点集分成两部分的划分），连接这个割的最小权重边一定属于某个最小生成树。算法每次选择当前未使用的最小权重边，并检查它是否会与已选边形成环。如果不形成环，就加入生成树。这等价于每次选择连接两个不同连通分量的最小权重边。

我们需要两个主要的数据结构：

  1. 一个并查集，用于高效地管理和查询顶点所属的连通分量，以及合并两个连通分量。
  2. 一个边的列表，按照权重非递减的顺序排序。

步骤 2：详细步骤分解

  1. 初始化：

    • 将结果集 \(T\) 设为空，用于存储最终构成最小生成树的边。
    • 对图中的每个顶点 \(v \in V\)，在并查集中将其初始化为一个独立的集合（即每个顶点自成一个连通分量）。
    • 将所有边 \(E\) 按照权重 \(w(e)\) 从小到大排序。

  2. 迭代处理每条边：

    • 按顺序遍历排序后的边列表。
    • 对于每条边 \(e = (u, v)\)：
      a. 使用并查集查询顶点 \(u\) 和 \(v\) 的根节点（即它们所属的连通分量代表）。
      b. 检查环：如果 \(u\) 和 \(v\) 的根节点相同，说明 \(u\) 和 \(v\) 已经在同一个连通分量中。加入边 \(e\) 会在这两个已连通的顶点间形成一条新边，从而产生环。因此，跳过这条边。
      c. 加入边：如果 \(u\) 和 \(v\) 的根节点不同，说明它们属于不同的连通分量。加入边 \(e\) 不会形成环，而且这是当前连接这两个分量的最小权重边（因为我们是按权重升序处理的）。因此，将边 \(e\) 加入结果集 \(T\)，并使用并查集合并 \(u\) 和 \(v\) 所在的集合。
    • 重复此过程，直到结果集 \(T\) 中包含 \(|V| - 1\) 条边（因为一棵树的边数等于顶点数减一）。此时，\(T\) 即为所求的最小生成树。

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

  • (A, B): 1
  • (A, C): 3
  • (B, C): 2
  • (B, D): 4
  • (C, D): 5
  1. 初始化：每个顶点自成一个集合。边按权重排序后顺序为：(A,B,1), (B,C,2), (A,C,3), (B,D,4), (C,D,5)。
  2. 处理 (A,B,1)：A 和 B 不在同一集合，加入此边。T = {(A,B)}。合并 A 和 B 的集合。
  3. 处理 (B,C,2)：B 的集合代表是 A（或 B），C 的集合代表是 C，不同。加入此边。T = {(A,B), (B,C)}。合并 B 和 C 的集合（现在 A, B, C 在同一连通分量）。
  4. 处理 (A,C,3)：A 和 C 现在在同一集合（根节点相同），加入会形成环（A-B-C-A），跳过。
  5. 处理 (B,D,4)：B 的集合代表是 A，D 的集合代表是 D，不同。加入此边。T = {(A,B), (B,C), (B,D)}。合并 B 和 D 的集合。
  6. 此时 T 已包含 3 条边（|V|-1=3），算法终止。最小生成树的总权重为 1+2+4=7。

步骤 4：算法正确性直观理解
Kruskal 算法本质上是不断将森林（初始时每个顶点是一棵树）合并，最终形成一棵树。由于每次都是加入当前连接两个不同树的最小权重边，这保证了局部的最优选择。该贪心策略的全局正确性可以通过“割性质”证明：算法加入的每条边，都是连接当时两个连通分量的最小权重边，而这样的边一定存在于某个最小生成树中。因此，最终构造出的树就是最小生成树。

步骤 5：复杂度分析
假设图有 \(|V| = n\) 个顶点，\(|E| = m\) 条边。

  • 排序：对边排序的时间复杂度为 \(O(m \log m)\)。
  • 并查集操作：每次 查找 和 合并 操作，在采用路径压缩和按秩合并优化后，近似为常数时间 \(O(\alpha(n))\)，其中 \(\alpha\) 是反阿克曼函数，增长极慢，可视为常数。我们最多进行 \(O(m)\) 次查找和 \(O(n)\) 次合并。
  • 总时间复杂度：主要由排序决定，为 \(O(m \log m)\)，通常也写作 \(O(m \log n)\)，因为 \(m\) 最多为 \(O(n^2)\)，所以 \(\log m\) 和 \(\log n\) 同阶。
  • 空间复杂度：存储边和并查集需要 \(O(m + n)\)。

总结
Kruskal 算法通过贪心策略，按权重递增顺序选择边，并利用并查集高效判断环，从而构建最小生成树。它易于实现，且在边数相对顶点数不太多（稀疏图）时非常高效，是解决最小生成树问题的经典算法之一。

最小生成树的 Kruskal 算法 题目描述 给定一个连通的无向图 \( G = (V, E) \)，其中 \( V \) 是顶点集合，\( E \) 是边集合。每条边 \( e \in E \) 都有一个权重（或成本） \( w(e) \)。目标是找到一个边的子集 \( T \subseteq E \)，使得 \( T \) 中的边连接所有顶点，并且形成一个树（即无环且连通），同时使 \( T \) 中所有边的权重之和最小。这样的树被称为图 \( G \) 的最小生成树。 Kruskal 算法就是一种经典的贪心算法，用于解决最小生成树问题。它的核心思想是： 按边权重从小到大的顺序考虑边，如果加入这条边不会在当前已选的边集中形成环，就将其加入生成树；否则跳过。直到选中了 \( |V| - 1 \) 条边为止。 解题过程循序渐进讲解 步骤 1：算法核心思想与准备 Kruskal 算法是一种贪心算法。其正确性基于一个关键性质： 对于任意一个割（将顶点集分成两部分的划分），连接这个割的最小权重边一定属于某个最小生成树 。算法每次选择当前未使用的最小权重边，并检查它是否会与已选边形成环。如果不形成环，就加入生成树。这等价于每次选择连接两个不同连通分量的最小权重边。 我们需要两个主要的数据结构： 一个 并查集 ，用于高效地管理和查询顶点所属的连通分量，以及合并两个连通分量。 一个 边的列表 ，按照权重非递减的顺序排序。 步骤 2：详细步骤分解 初始化 ： 将结果集 \( T \) 设为空，用于存储最终构成最小生成树的边。 对图中的每个顶点 \( v \in V \)，在并查集中将其初始化为一个独立的集合（即每个顶点自成一个连通分量）。 将所有边 \( E \) 按照权重 \( w(e) \) 从小到大排序。 迭代处理每条边 ： 按顺序遍历排序后的边列表。 对于每条边 \( e = (u, v) \)： a. 使用并查集查询顶点 \( u \) 和 \( v \) 的根节点（即它们所属的连通分量代表）。 b. 检查环 ：如果 \( u \) 和 \( v \) 的根节点相同，说明 \( u \) 和 \( v \) 已经在同一个连通分量中。加入边 \( e \) 会在这两个已连通的顶点间形成一条新边，从而产生环。因此，跳过这条边。 c. 加入边 ：如果 \( u \) 和 \( v \) 的根节点不同，说明它们属于不同的连通分量。加入边 \( e \) 不会形成环，而且这是当前连接这两个分量的最小权重边（因为我们是按权重升序处理的）。因此，将边 \( e \) 加入结果集 \( T \)，并使用并查集合并 \( u \) 和 \( v \) 所在的集合。 重复此过程，直到结果集 \( T \) 中包含 \( |V| - 1 \) 条边（因为一棵树的边数等于顶点数减一）。此时，\( T \) 即为所求的最小生成树。 步骤 3：举例说明 考虑一个简单图，顶点集 \( 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)。 处理 (A,B,1) ：A 和 B 不在同一集合，加入此边。T = {(A,B)}。合并 A 和 B 的集合。 处理 (B,C,2) ：B 的集合代表是 A（或 B），C 的集合代表是 C，不同。加入此边。T = {(A,B), (B,C)}。合并 B 和 C 的集合（现在 A, B, C 在同一连通分量）。 处理 (A,C,3) ：A 和 C 现在在同一集合（根节点相同），加入会形成环（A-B-C-A），跳过。 处理 (B,D,4) ：B 的集合代表是 A，D 的集合代表是 D，不同。加入此边。T = {(A,B), (B,C), (B,D)}。合并 B 和 D 的集合。 此时 T 已包含 3 条边（|V|-1=3），算法终止。最小生成树的总权重为 1+2+4=7。 步骤 4：算法正确性直观理解 Kruskal 算法本质上是不断将森林（初始时每个顶点是一棵树）合并，最终形成一棵树。由于每次都是加入当前连接两个不同树的最小权重边，这保证了局部的最优选择。该贪心策略的全局正确性可以通过“割性质”证明：算法加入的每条边，都是连接当时两个连通分量的最小权重边，而这样的边一定存在于某个最小生成树中。因此，最终构造出的树就是最小生成树。 步骤 5：复杂度分析 假设图有 \( |V| = n \) 个顶点，\( |E| = m \) 条边。 排序 ：对边排序的时间复杂度为 \( O(m \log m) \)。 并查集操作 ：每次 查找 和 合并 操作，在采用路径压缩和按秩合并优化后，近似为常数时间 \( O(\alpha(n)) \)，其中 \( \alpha \) 是反阿克曼函数，增长极慢，可视为常数。我们最多进行 \( O(m) \) 次查找和 \( O(n) \) 次合并。 总时间复杂度 ：主要由排序决定，为 \( O(m \log m) \)，通常也写作 \( O(m \log n) \)，因为 \( m \) 最多为 \( O(n^2) \)，所以 \( \log m \) 和 \( \log n \) 同阶。 空间复杂度 ：存储边和并查集需要 \( O(m + n) \)。 总结 Kruskal 算法通过贪心策略，按权重递增顺序选择边，并利用并查集高效判断环，从而构建最小生成树。它易于实现，且在边数相对顶点数不太多（稀疏图）时非常高效，是解决最小生成树问题的经典算法之一。