首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
现有一个解决无向连通图的最小生成树的一种方法如下: 将图中所有边按权重从大到小排序为(e1,e2,…,en); i=1: while(所剩边数>=顶点数){ 从图中删去ei; 若图不再连通,则恢复ei; i=
现有一个解决无向连通图的最小生成树的一种方法如下: 将图中所有边按权重从大到小排序为(e1,e2,…,en); i=1: while(所剩边数>=顶点数){ 从图中删去ei; 若图不再连通,则恢复ei; i=
admin
2013-12-31
33
问题
现有一个解决无向连通图的最小生成树的一种方法如下:
将图中所有边按权重从大到小排序为(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
学硕统考专业
相关试题推荐
简述戴高乐独立自主外交政策产生的背景、内容和意义。
论述十字军运动(十字军东征)发生的背景、过程及其影响。
文艺复兴时期,系统提出了国家主权理论的政治思想家是()。
下列关于明朝设立内阁的相关表述不正确的是()。
克里特文明的文字类型是()。
在西北地区,西北野战军采取了蘑菇战术与敌人周旋,这实际上是()。
院系调整
图的D搜索类似于BFS,不同之处在于使用栈代替BFS中的队列,入/出队列的操作作为入/出栈的操作,即当一个顶点的所有邻接结点被搜索后,下一个搜索出发点应该是最近入栈(栈顶)的顶点。(1)用邻接表作为存储结构,写一个D搜索算法;(2)用D搜索方法
高度为7的AVL树最少有()个结点。
给定单链表的结点结构typedefstructnode*link;structnode{intitem,linknext;);将两个升序单链表归并为一个升序单链表。
随机试题
喷油器的燃油泄漏量在1min内少于()滴,否则应予以更换。
革命在社会发展中的重要作用是()
A.温度-3℃,相对湿度60%~85%B.温度0~1℃,相对湿度95%~98%C.温度-2℃,相对湿度85%~88%D.温度-5℃,相对湿度90%~95%E.温度-1~1℃,相对湿度60%~85%鲜肉的适宜冷藏条件
A.0.1%B.0.5%C.1%D.2%E.3%用于消毒口腔及创口的氯己定液浓度为
任何建设项目在运营过程中都会产生费用,其目的是为了取得一定的效果,所支出的费用包括()等。
监理业务具有一定的程序性,其流程包括:①接受监理任务;②确认或委派项目总监理工程师,③成立项目监理机构;④收集有关工程资料;⑤按合同编制监理规划或分项分阶段编制监理实施细则;⑥监理工作交底会(第一次监理例会);⑦实施监理工作;⑧工程初验;⑨监理总结、建档;
在OSI参考模型中,物理层的功能是()。
从所给的四个选项中,选择最合适的一个填入问号处,使之呈现一定的规律性:
设曲线L位于xOy平面的第一象限内,L上任一点M处的切线与y轴总相交,交点记为A.已知,且L过点,求L的方程.
Diana:Lookatthosestrangely-dressedkids.Whataretheydoingthere?Arthur:Don’tyouknow?TodayistheHalloweenDay.【D1】_
最新回复
(
0
)