切分定理疑惑
来源：11-4 切分定理
慕设计8552030
2020-03-17
使用kruskal算法时，如果选择最小的边构成环时，不属于最小生成树的边，但对于切分定理来说，这个最小的边是某个切分的最小的横切边，一定属于最小生成树的边，表面上看岂不是矛盾的吗？应该是哪里我理解的有问题，请bobo老师解惑，谢谢？
写回答
1回答
-
赞问题！
一个图的最小生成树，可能不只有一个（当然也可能只有一个）。
如果你的在使用 kruskal 算法的过程中，所选择的边，是某一个切分的最小边，且这个边构成环的话，说明，这个边可能出现在其他形态的最小生成树上，但是对于你使用 kruskal 算法已经构造的这个部分最小生成树来说，它已经不可能属于最终结果了。
你可以试着根据你的想法，构造一些测试用例，其实，最典型的情况就是：图中的所有的边都一样，他们都是整张图的最短边：）
继续加油！：）
012020-03-18
相似问题