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

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

admin2013-12-31  80
问题 现有一个解决无向连通图的最小生成树的一种方法如下：
    将图中所有边按权重从大到小排序为(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
本试题收录于： 计算机408题库学硕统考专业分类
0

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)