首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
现有一个解决无向连通图的最小生成树的一种方法如下: 将图中所有边按权重从大到小排序为(e1,e2,…,en); i=1: while(所剩边数>=顶点数){ 从图中删去ei; 若图不再连通,则恢复ei; i=
现有一个解决无向连通图的最小生成树的一种方法如下: 将图中所有边按权重从大到小排序为(e1,e2,…,en); i=1: while(所剩边数>=顶点数){ 从图中删去ei; 若图不再连通,则恢复ei; i=
admin
2013-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
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
下列选项中对中国新民主主义革命和旧民主主义革命的比较,正确的是()①是中国资产阶级民主革命进程总的两个阶段②两者的根本区别在于领导阶级的不同③两者的指导思想和革命前途不同④两者的革命性质和根本任务没有变化
论述王守仁心学思想的形成背景及主要观点
论述英国都铎王朝加强专制统治的过程及措施
试总结苏联二三十年代社会主义建设的特点、成就及存在的问题
李鸿章奏请在天津设立的北洋水师学堂的落成时间是()。
日本在《二十一条》中提出:“中国沿海岛屿不得租于他国。”其真实目的是()。
西南军阀跟随孙中山拥护护法运动的目的是()。
简析义和团的“扶清灭洋”口号。
美国主张建立国际联盟的主要目的是()。
阅读以下史料,结合相关背景知识,分析古巴比伦社会的等级制度和奴隶制度。《汉谟拉比法典》(节录)第七条自由民从自由民之子或自由民之奴隶手中买得或为之保管银或金。或奴隶,或女奴,或牛,或羊,或驴,或不论任何物,而无证人及契约者,是为窃贼,
随机试题
艺术品赖以在时空中存在的物质实体和媒介是指()
扩张型心肌病与心包积液的鉴别主要根据
桥梁用板式橡胶支座抗剪黏结试验最大剪应力为2MPa。()
在集装箱班轮运输中,进口货物的收货人没有在规定的时间内及时将空箱交还班轮公司,则收货人要向船公司支付滞箱费。()
下列关于有限责任公司股东行使股权买回请求权的表述中,正确的是()。
税务机关对单价()元以下的其他生活用品,不采取税收保全措施。
测量臀围。
假如一个教师把大量的时间用于与学生搞好个人关系上,那么他处于教师成长的()。
下列给定程序中,函数fun的功能是:将s所指字符串中位于奇数位置的字符或ASCII码值为偶数的字符依次放入t所指数组中。例如,字符串中的数据为“AABBCCDDEEFF”,则输出应当是“ABBCDDEFF”。请改正程序中的错误,使它能得出正确的结
He______intotheofficebuildingwhenthefirebellrang.
最新回复
(
0
)