首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
有人提出这样的一种从图G中顶点u开始构造最小生成树的方法。 假设G=(V,E)是一个具有n个顶点的带权连通无向图,T=(U,TE)是G的最小生成树,其中U是T的顶点集,TE是T的边集,则由G构造从起始顶点u出发的最小生成树T的步骤如下: 重复以下
有人提出这样的一种从图G中顶点u开始构造最小生成树的方法。 假设G=(V,E)是一个具有n个顶点的带权连通无向图,T=(U,TE)是G的最小生成树,其中U是T的顶点集,TE是T的边集,则由G构造从起始顶点u出发的最小生成树T的步骤如下: 重复以下
admin
2014-04-17
32
问题
有人提出这样的一种从图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题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
论述《国联盟约》的出台背景、主要内容及影响
分析第二次工业革命的特点及历史影响。
简述战后西欧经济的变化过程。
国民政府对日宣战的时间是()。
下列著作被人们称为17世纪物理学、数学的百科全书,并标志着经典力学体系的完成的是()。
中国历史上第一部资产阶级革命法典《临时约法》公布的时间是()。
中共十六届五中全会提出,建设社会主义新农村的要求是生产发展和()。
简述当代科学技术革命兴起的背景、特点及影响。
1948年,南斯拉夫对从苏联照搬来的“行政命令式的国家集权式”体制进行改革逐步形成有自己特色的建设社会主义的理论和方法,其核心是()。
著名的绥靖政策文件《霍尔—赖伐尔协定》是英、法与意大利签订的,密谋发动()。
随机试题
在关系窗口中,双击两个表之间的连接线,会出现()。
质地最硬的肿瘤是
患者进行X线检查,测量其髋CE角为多少时考虑先天性髋关节脱位先天性髋关节脱位成年后最常见的并发症是
当归主要含有黄连主要含有
全面竣工验收的阶段划分为()。
人口普查统计数据可能存在的误差来源有( )。
单位将不动产无偿赠与他人,视同销售不动产征收营业税,其纳税义务发生时间是()。
(2010年单选20)下列行为中,应以抗税罪定罪处罚的是()。
设f(x)在(-∞,a)内可导,,求证:f(x)在(-∞,a)内至少有一个零点.
将较长的数据类型转换为较短的整数类型,要进行()。
最新回复
(
0
)