首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
现有一个解决无向连通图的最小生成树的一种方法如下: 将图中所有边按权重从大到小排序为(e1,e2,…,en); i=1: while(所剩边数>=顶点数){ 从图中删去ei; 若图不再连通,则恢复ei; i=
现有一个解决无向连通图的最小生成树的一种方法如下: 将图中所有边按权重从大到小排序为(e1,e2,…,en); i=1: while(所剩边数>=顶点数){ 从图中删去ei; 若图不再连通,则恢复ei; i=
admin
2013-12-31
83
问题
现有一个解决无向连通图的最小生成树的一种方法如下:
将图中所有边按权重从大到小排序为(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
学硕统考专业
相关试题推荐
文艺复兴运动兴起的时间是()。
下列不是空想社会主义产生的历史背景的是()。
简述德意志帝国从建立到1900年前后主要的外交政策。(华南师范大学2006年世界近现代史真题)
彻底肃清氏族制残余,标志雅典国家的正式形成的事件是()。
明万历年间使地主与农民之间仅仅存在着单纯的经济关系而没有人身依附关系的是()。
国民政府对日宣战的时间是()。
下列著作被人们称为17世纪物理学、数学的百科全书,并标志着经典力学体系的完成的是()。
二战后,美国推行“冷战”政策的表现有()①向西欧提供经济援助②支持联邦德国崛起③以联合国名义直接出兵朝鲜④成立北大西洋公约组织
中共七届三中全会以后进行的工商业合理调整,其核心内容是调整()。
以数组Data[m+1]作为循环队列SQ的存储空间,front为头指针,rear为队尾指针,则执行出队操作的语句是()。
随机试题
设函数,在x=0处连续,则()。
建设工程项目总承包合同中对总承包的内容规定一般包括从工程立项到()工程建设全过程。
关于可交换债券,下列说法正确的有( )。
人力资源管理对组织中所有的管理人员都极为重要,体现在()。
根据增值税法律制度的规定,下列各项中,属于应当征收增值税的混合销售行为的有()。
读书同看电影、看录像、听音乐会是那样的不同:后者是一块巨大的生日蛋糕,可以美味地共享;前者只是孤灯下的一盏清茶,只可独啜,倾听一个遥远的灵魂对你一个人的窃窃私语,你啪地合上书,就把一代先哲幽禁在里面。但你忍不住又要打开它,穿越历史的灰尘与他对话。这段话主要
官渡之战、赤壁之战、淝水之战这三次著名战役的相似之处是()。
在西方经济发展的萧条期,消费需求的萎缩导致许多企业解雇职工甚至倒闭,在萧条期,被解雇的职工很难找到新的工作,这就增加了失业人数。萧条之后的复苏,是指消费需求的增加和社会投资能力的扩张,这种扩张要求增加劳动力。但是经历了萧条之后的企业主大都丧失了经商的自信,
设f(x)在[一1,1]上可导,f(x)在x=0处二阶可导,且f’(0)=0,f’’(0)=4.求
使用约束可以保证数据库中数据的正确性,其中【8】约束允许出现空值但不允许出现重复值。
最新回复
(
0
)