首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
现有一个解决无向连通图的最小生成树的一种方法如下: 将图中所有边按权重从大到小排序为(e1,e2,…,en); i=1: while(所剩边数>=顶点数){ 从图中删去ei; 若图不再连通,则恢复ei; i=
现有一个解决无向连通图的最小生成树的一种方法如下: 将图中所有边按权重从大到小排序为(e1,e2,…,en); i=1: while(所剩边数>=顶点数){ 从图中删去ei; 若图不再连通,则恢复ei; i=
admin
2013-12-31
30
问题
现有一个解决无向连通图的最小生成树的一种方法如下:
将图中所有边按权重从大到小排序为(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
学硕统考专业
相关试题推荐
婆罗门教的经典和主要教义。
“冷战”局面的形成是由于()①美国试图称霸世界②苏联政治军事力量增强③欧亚社会主义阵营形成④美苏展开核军备竞赛
西汉时期,张骞第一次出使西域的主要目的是()
下列选项中,不是由晁错提出的是()
西汉初年,反驳刘邦“马上治天下”的说法,并向汉帝国治国献策的是()。
1895年发现X射线,拉开物理学革命序幕的科学家是()。
1948年,南斯拉夫对从苏联照搬来的“行政命令式的国家集权式”体制进行改革逐步形成有自己特色的建设社会主义的理论和方法,其核心是()。
西周前期,曾先后向东、南和西三个方向扩张,其中向南扩张主要发生在()
对斯大林时期形成的高度集中的社会主义经济政治体制的叙述,不确切的是()。
提出电磁感应定律的是物理学家()。
随机试题
刀工在烹饪中的作用是_______。
A.皮肤及其网状淋巴管的急性炎症B.一个毛囊及其所属皮脂腺的急性化脓性感染C.皮下、筋膜下蜂窝组织急性炎症D.多个相邻毛囊及其所属皮脂腺的急性化脓陛感染E.皮肤及其网状淋巴管的慢性炎症疖()
复发性阿弗他溃疡的治疗原则是
选择肌内注射部位的原则是()
间接融资的优点在于()。
留置作为一种担保方式,只能通过( )产生留置权。
关于场内证券交易市场,以下描述不正确的是()。
已知流体的流速为ν=(2x+z)i+zk,流体的密度为μ=1.求流体在单位时间内流出曲面∑:z=x2+y2,(0≤z≤1)的流量,其中∑的法向量与z轴正向夹角为锐角.
域名MH.BIT.EDU.CN中主机名是()。
AstudyconductedbyanAustralianscienceagencyhasdiscoveredsignsthatthecountry’sancientAboriginesmayhavebeenthew
最新回复
(
0
)