图论——七、最小生成树唯一性判定

判定最小生成树是否唯一的思路： 1、对图中每条边，扫描其他边，如果存在相同权值的边，则对该边进行标记；
2、然后用Kruskal（或者PRIM）算法求MST（最小生成树）；
3、求得MST后，如果该MST中未包含做了标记的边，即可判定MST唯一；如果包含作了标记的边，则依次去掉这些边再求MST，如果求得的MST权值和原MST权值相同，即可判定MST不唯一。
如下图所示：