无向连通图中顶点最轻邻边是否属于某棵MST？思路正确性求证

你的结论是完全正确的，但“最小生成树会选取所有最轻边”这个思路表述得有点模糊，咱们可以结合算法原理把逻辑理得更严谨些：

首先明确定义：无向连通图中，顶点v的最轻邻边e，指的是所有连接v与其他顶点的边里，权重最小的那条。

从Prim算法的角度理解 #

Prim算法是从一个起始顶点开始，逐步扩展MST的顶点集合，每次选择当前集合与外部顶点之间的最轻边加入树中。如果我们把起始顶点设为v，那第一步必然会选中e（因为它是v的最轻邻边），这样e就直接出现在这棵构造出来的MST里了，这就证明了e至少属于这一棵MST。

用反证法进一步验证 #

假设e不属于任何一棵MST，那我们任取一棵MST T，把e加入T中会形成一个环。在这个环里，v必然还连接着另一条边e'（否则环无法形成）。因为e是v的最轻邻边，所以weight(e) ≤ weight(e')。

如果我们把T中的e'移除，替换成e，得到的新树T'依然是一棵生成树，而且总权重不会超过T的总权重。这说明T'也是一棵MST，而e在T'里——这和我们“e不属于任何MST”的假设矛盾，所以e一定属于某棵MST。

最后补充一点：你提到的“选取所有最轻边”其实不太准确，因为多个顶点的最轻邻边可能形成环，这时候这类边不能全部加入MST（否则会出现环，不符合树的定义），但单个顶点的最轻邻边，一定能在某棵MST中找到它的位置。

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