两种图G=(V,E)算法是否必生成最小生成树？求反例验证

算法一分析 #

算法一是经典的Kruskal算法，它必然能返回最小生成树：

• 按边权从小到大排序，保证每次优先选择当前可选的最小权值边；
• 仅当加入边后不形成环时才保留，确保最终的集合T是无环的连通子图；
• 当T包含|V|-1条边时，就构成了图的最小生成树，完全符合最小生成树的贪心选择性质。

算法二分析 #

算法二是基于反向贪心逻辑的最小生成树算法，同样必然返回最小生成树：

• 按边权从大到小排序，从全边集开始尝试移除最大权值的边；
• 仅当移除后边集仍保持连通时才删除，这意味着被移除的边是某个环中的最大权值边——而根据最小生成树的环性质：任意环中权值最大的边一定不在最小生成树中；
• 当T被精简到|V|-1条边时，剩余的边集就是无环的连通子图，即最小生成树。

结论 #

两种算法都必然返回图的最小生成树，不存在反例。

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