首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
现有一个解决无向连通图的最小生成树的一种方法如下: 将图中所有边按权重从大到小排序为(e1,e2,…,en); i=1: while(所剩边数>=顶点数){ 从图中删去ei; 若图不再连通,则恢复ei; i=
现有一个解决无向连通图的最小生成树的一种方法如下: 将图中所有边按权重从大到小排序为(e1,e2,…,en); i=1: while(所剩边数>=顶点数){ 从图中删去ei; 若图不再连通,则恢复ei; i=
admin
2013-12-31
86
问题
现有一个解决无向连通图的最小生成树的一种方法如下:
将图中所有边按权重从大到小排序为(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
学硕统考专业
相关试题推荐
下列对于凡尔赛和约的表述不正确的是()
简述第二次科技革命的主要内容。
论述清朝在康雍乾时期为巩固多民族统一国家所做的努力
下列不属于苏联高度集中的经济政治体制产生的条件的是()。
下列对春秋时期各国称霸的顺序描述错误的选项是()
下列选项中,不是由晁错提出的是()
外国侵略者通过不平等条约取得的特权中,按时间先后顺序排列应是()。①外国商船和军舰可以在长江各口岸自由航行②外国人可以在通商口岸开设工厂③可在通商口岸建立教堂④领事裁判权和片面最惠国待遇
战国初期,上党地区在下列哪一个国家的控制范围之内?()
简述美苏争霸的三个阶段,并分析其影响与教训。
西周前期,曾先后向东、南和西三个方向扩张,其中向南扩张主要发生在()
随机试题
计算机教学属于________的教学方式。
光的干涉和衍射现象反映了光的()。[2013年真题]
极重交通荷载等级公路面层混凝土用的粗集料质量应不低于()的要求。
下列属于电话营销优点的是()。
根据下面材料回答问题。下列关于2009年图中各省市普通高中情况的描述,与资料相符的是()。
测验的使用者利用()可将原始分数转换为与其对应的导出分数,从而对测验的分数做出有意义的解释。
截至2011年4月21日22时,沪深两市已有534家上市公司公布第一季度财报。这534家公司实现营业总收入4572.78亿元.同比增长30.74%。……已公布一季报的创业板公司有71家,实现营业收入80.08亿元,同比增长73.60%:实现净利润13.16
下列关于光以太网技术特征的描述中,错误的是()。
Whattimeisitnow?
PASSAGEONEWhatdoes"spell"inParagraph1mean?
最新回复
(
0
)