Kruskal算法是否能求得最小瓶颈生成树？如何证明其正确性？

核心概念前置 #

先明确统一术语定义，避免歧义：

• 给定无向带权连通图 $G=(V,E)$，边权函数为 $w:E\rightarrow\mathbb{R}$
• 生成树：$G$ 的连通无环生成子图，包含全部 $|V|$ 个顶点，共含 $|V|-1$ 条边
• 最小瓶颈生成树（Minimum Bottleneck Spanning Tree, MBST）：对于生成树 $T$，定义其瓶颈值为树中边的最大权值 $\max_{e\in T}w(e)$；MBST就是所有生成树中瓶颈值最小的那类生成树，记全局最小瓶颈值为 $b^*$
• Kruskal算法标准流程：将所有边按权值非降序排序，依次遍历每条边，若当前边连接两个互不连通的顶点分量，则将该边加入生成树边集，直到所有顶点归入同一个连通分量时停止。

对第一个问题的明确答复 #

Kruskal算法完全可以找到图的最小瓶颈生成树，实际上该算法输出的任意生成树（存在等权边时可能有多个合法输出）都必然是MBST，具体证明见下一问的推导。

Kruskal算法总能生成MBST的证明 #

我们通过反证法结合算法执行的固有逻辑完成证明，不需要依赖最小生成树（MST）的额外性质：

1. 记Kruskal算法输出的生成树为 $T_K$，设其瓶颈边（$T_K$ 中权值最大的边）为 $e_b$，对应瓶颈值为 $w(e_b)=b_K$。
2. 反证假设：若 $T_K$ 不是MBST，则必定存在另一棵合法生成树 $T'$，其瓶颈值 $b' < b_K$——换句话说，$T'$ 中所有边的权值都严格小于 $b_K$。
3. 回到Kruskal的执行过程：在算法选中 $e_b$ 之前，所有已经被加入生成树的边权值都严格小于 $b_K$，此时全图被划分为至少2个互不连通的分量，记为 $C_1,C_2,\dots,C_k$（$k\geq2$）；$e_b$ 被选中的原因，就是它连接了其中两个不同的分量，不妨设为 $C_i$ 和 $C_j$。
4. 根据反证假设，$T'$ 仅用权值小于 $b_K$ 的边就连通了全图，那 $T'$ 中必然存在至少一条边 $e'$ 连接 $C_i$ 和 $C_j$——如果不存在这样的边，仅用权值小于 $b_K$ 的边根本无法连通 $C_i$ 和 $C_j$，和 $T'$ 是连通生成树的前提矛盾，且显然 $w(e') < b_K$。
5. 这里直接导出矛盾：Kruskal是按权值从小到大遍历边的，权值更小的 $e'$ 一定比 $e_b$ 更早被处理；而遍历到 $e_b$ 时 $C_i$ 和 $C_j$ 仍然是两个独立分量，说明遍历到更早出现的 $e'$ 时，$C_i$ 和 $C_j$ 肯定也没有连通，按照算法规则 $e'$ 会被直接选中加入生成树，提前把 $C_i$ 和 $C_j$ 合并，后续根本不会再选择 $e_b$，这和 $e_b$ 属于 $T_K$ 边集的事实冲突。
6. 因此反证假设不成立，不存在瓶颈值小于 $b_K$ 的生成树，即 $b_K = b^*$，$T_K$ 就是合法的MBST。

补充说明 #

• 我们熟知的性质“所有MST都是MBST”是上述结论的一个推论：Kruskal算法本身是经典的MST构造算法，其输出自然是MST，而上述证明没有用到MST总权值最小的性质，直接从算法流程和MBST的定义出发完成了验证。
• 从另一个角度理解：Kruskal算法第一次让全图连通时加入的边的权值，恰好等于图的全局最小瓶颈值 $b^*$——这也是所有MBST构造算法的核心判定标准。

内容的提问来源于stack exchange，提问作者Ofekino97