加载中…图论——七、最小生成树唯一性判定
(2014-04-19 19:38:45)
标签：
最小生成树唯一性it |
分类： 图论 |
判定最小生成树是否唯一的思路：
1、对图中每条边，扫描其他边，如果存在相同权值的边，则对该边进行标记；
2、然后用Kruskal（或者PRIM）算法求MST（最小生成树）；
3、求得MST后，如果该MST中未包含做了标记的边，即可判定MST唯一；如果包含作了标记的边，则依次去掉这些边再求MST，如果求得的MST权值和原MST权值相同，即可判定MST不唯一。
如下图所示：
喜欢
0
赠金笔