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

admin2017-11-20 35

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

选项

答案此方法不能求得最小生成树。例如，对于图7-11a所示的带权连通无向图，按照上述方法从顶点0开始求得的结果为图7-11b所示的树，显然它不是最小生成树，正确的最小生成树如图7-11c所示。在有些情况下，上述方法甚至无法求得最小生成树。例如对于图7-11d所示的带权连通无向图，从顶点0出发，找到顶点1(边(0，1))，从顶点1出发，找到顶点3(边(1，3))，再从顶点3出发，找到顶点0(边(3，0))，这样构成回路，就不能求得最小生成树了。 [*]

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

1948年3月，英国、法国、比利时、荷兰、卢森堡5国缔结了5国《合作和集体防御条约》，即()，这是一项以军事同盟为核心的包括政治、经济、文化的合作条约。

下列不属于战时共产主义政策内容的是()。

改革开放以后，我国农村产业结构巨大的转变表现在()。

著名的绥靖政策文件《霍尔—赖伐尔协定》是英、法与意大利签订的，密谋发动()。

武则天时期，为了管理天山以北的广大区域而设立了()。

加尔文教传播到法国后，其信仰者被称为()。

()是清代管理边疆少数民族地区事务的机关，也掌管一部分外交事务。

IP数据报的报文格式如下图所示。在没有选项和填充的情况下，报头长度域的值为()。

某网络的拓扑结构由下图所示，其中顶点表示路由器。该网络的路由器采用了链路状态路由算法，在某一时刻各个路由器发送的链路状态如下：A：B(1)，D(3)B：A(1)，D(1)，C(3)，E(5)C：B(3)，D(1)D：A(3)，B(1

已知某CPU有16根地址线、8根数据线，并用MREQ作为访存控制信号(低电平有效)。现有下列存储芯片：1K×4位ROM、2K×4位ROM、4K×8位ROM、4K×8位RAM、8K×4位RAM、8K×8位RAM和非门、与非门、或非门若干，如下图所

[*]

Theelephantistheonlyanimalintheworldwithatrunk(theverylongnoseofanelephant),Itusesitstrunk【21】manyways.I

5，7，2’，4’-四羟基黄酮5，7，3’，4，-四羟基二氢黄酮

依据我国《商业银行法》的规定，下列表述错误的是：()。

应用建设工程项目管理信息系统的主要意义包括()。

某公共建筑设有8台火灾报警控制器，在竣工验收时，应抽取()台进行功能检验。

宋明理学与先秦儒学相比，其重大发展有()。①吸收了佛教和道教的思想②完成了理论化、思辨化的过程③封建的伦理道德行为规范形成④具有浓郁的人文主义精神

有三个人的年龄各不相同，且他们的年龄总和为93岁，其中有2个人的年龄是平方数。如果倒退16年，这三个人中仍有2个人的年龄是平方数。则这三个人的年龄分别是()。

设窗体上有1个水平滚动条，已经通过属性窗口把它的Max属性设置为1，Min属性设置为100。下面叙述中正确的是(　　)。

计算机408

学硕统考专业

1948年3月，英国、法国、比利时、荷兰、卢森堡5国缔结了5国《合作和集体防御条约》，即()，这是一项以军事同盟为核心的包括政治、经济、文化的合作条约。

下列不属于战时共产主义政策内容的是()。

改革开放以后，我国农村产业结构巨大的转变表现在()。

著名的绥靖政策文件《霍尔—赖伐尔协定》是英、法与意大利签订的，密谋发动()。

武则天时期，为了管理天山以北的广大区域而设立了()。

加尔文教传播到法国后，其信仰者被称为()。

()是清代管理边疆少数民族地区事务的机关，也掌管一部分外交事务。

IP数据报的报文格式如下图所示。在没有选项和填充的情况下，报头长度域的值为()。

某网络的拓扑结构由下图所示，其中顶点表示路由器。该网络的路由器采用了链路状态路由算法，在某一时刻各个路由器发送的链路状态如下：A：B(1)，D(3)B：A(1)，D(1)，C(3)，E(5)C：B(3)，D(1)D：A(3)，B(1

已知某CPU有16根地址线、8根数据线，并用MREQ作为访存控制信号(低电平有效)。现有下列存储芯片：1K×4位ROM、2K×4位ROM、4K×8位ROM、4K×8位RAM、8K×4位RAM、8K×8位RAM和非门、与非门、或非门若干，如下图所

[*]

Theelephantistheonlyanimalintheworldwithatrunk(theverylongnoseofanelephant),Itusesitstrunk【21】manyways.I

5，7，2’，4’-四羟基黄酮5，7，3’，4，-四羟基二氢黄酮

依据我国《商业银行法》的规定，下列表述错误的是：()。

应用建设工程项目管理信息系统的主要意义包括()。

某公共建筑设有8台火灾报警控制器，在竣工验收时，应抽取()台进行功能检验。

宋明理学与先秦儒学相比，其重大发展有()。①吸收了佛教和道教的思想②完成了理论化、思辨化的过程③封建的伦理道德行为规范形成④具有浓郁的人文主义精神

有三个人的年龄各不相同，且他们的年龄总和为93岁，其中有2个人的年龄是平方数。如果倒退16年，这三个人中仍有2个人的年龄是平方数。则这三个人的年龄分别是()。

设窗体上有1个水平滚动条，已经通过属性窗口把它的Max属性设置为1，Min属性设置为100。下面叙述中正确的是( )。

设窗体上有1个水平滚动条，已经通过属性窗口把它的Max属性设置为1，Min属性设置为100。下面叙述中正确的是(　　)。