有人提出这样的一种从图G中顶点u开始构造最小生成树的方法。假设G=(V，E)是一个具有n个顶点的带权连通无向图，T=(U，TE)是G的最小生成树，其中U是T的顶点集，TE是T的边集，则由G构造从起始顶点u出发的最小生成树T的步骤如下：重复以下

admin2014-04-17 34

问题有人提出这样的一种从图G中顶点u开始构造最小生成树的方法。
假设G=(V，E)是一个具有n个顶点的带权连通无向图，T=(U，TE)是G的最小生成树，其中U是T的顶点集，TE是T的边集，则由G构造从起始顶点u出发的最小生成树T的步骤如下：
重复以下步骤n～1次，使得其他n一1个顶点被加入到U中。从候选边中挑选权值最小的边加入到TE，设该边在V-U中的顶点是v，将v加入U中。考查顶点v，将v与V-U顶点集中的所有边作为新的候选边。若此方法求得的T是最小生成树，请予以证明。若不能求得最小生成树，请举出反例。

选项

答案例如对于图7—8d所示的带权连通无向图，从顶点0出发，找到顶点1(边(0，1))，从顶点1出发，找到顶点3(边(1，3))，再从顶点3出发，找到顶点0(边(3，0))，这样构成回路，就不能求得最小生成树了。 [*]

解析

转载请注明原文地址:https://kaotiyun.com/show/oYxi777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

简要分析在蒸汽时代资本主义的决定性的胜利。

我国第一部系统的史学理论著作是()。

清初设置的两个“办事大臣”是()。①宁古塔②西宁③库伦④西藏

1939年8月23日，苏德双方签了()和《秘密附属议定书》，划定了双方在东欧的势力范围。这一条约使德国得以进攻波兰，使第二次世界大战终于爆发。

下列不属于苏联高度集中的经济政治体制产生的条件的是()。

维也纳会议争论的焦点问题是()。

二战后世界经济发展变化迅速，这种变化主要表现在()。①国际金融体系和贸易体系的形成②国家垄断资本主义的空前发展③形成以美苏冷战为特征的两极格局④科学技术推动生产力发展更为迅速

以下选项不属于希腊城邦的形成方式和途径的是()。

下列有关《布列斯特和约》的说法中，错误的一项是()。

假设某计算机的存储系统由Cache和主存组成j某程序执行过程中访存1000次，其中访问Cache缺失(未命中)50次，则Cache的命中率是()。

支气管哮喘的基础病变是

男性。30岁。3月前患胸膜炎。经抽液，异烟肼加利福平、吡嗪酰胺治疗2个月胸水吸收。2周来发热、咳嗽、痰血。X线检查示右上肺浸润性阴影。痰抗酸杆菌阳性。宜用哪种抗结核方案

某女，35岁，已婚，性交后阴道少量出血，妇查阴道畅，分泌物少，宫颈充血，表面呈颗粒状，糜烂面占宫颈面积1/4，下列哪项不正确

当医院出现医院感染散发病例时，经治医师应填表报告医院感染管理科的时间是

建筑材料的基本性质包括()。

关于价值工程活动，下列说法中正确的是()。

下列施工生产要素的质量控制内容中，属于工艺方案质量控制的是()。

下列公式中含有不正确单元格引用形式的是()。

在1，2，3，4，5这五个数字组成的没有重复数字的三位数中，各位数字之和为奇数的共有()。