现有一个解决无向连通图的最小生成树的一种方法如下: 将图中所有边按权重从大到小排序为(e1,e2,…,en); i=1: while(所剩边数>=顶点数){ 从图中删去ei; 若图不再连通,则恢复ei; i=

admin2013-12-31  37

问题 现有一个解决无向连通图的最小生成树的一种方法如下:
    将图中所有边按权重从大到小排序为(e1,e2,…,en);
    i=1:
    while(所剩边数>=顶点数){
    从图中删去ei;
    若图不再连通,则恢复ei;
    i=i+1;
    }
    请问上述方法能否求得原图的最小生成树?若该方法可行,请证明之;否则请举例说明。

选项

答案题目中方法能求得最小生成树。证明如下: (1)从算法中while(所剩边数≥顶点数)来看,循环到边数比顶点数少1(即n-1)停止,这符合n个顶点的连通图的生成树有n-1条边的定义; (2)由于边是按权值从大到小排序,删去的边是权值大的边,结果的生成树必是最小生成树; (3)算法中“若图不再连通,则恢复ei”,含义是必须保留使图连通的边,这就保证了是生成树,否则或者是有回路,或者成了连通分量,均不再是生成树。 所以,题目中方法可以求得图的最小生成树。

解析
转载请注明原文地址:https://kaotiyun.com/show/kSxi777K
0

最新回复(0)