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

admin2017-11-20 32

问题有人提出这样的一种从图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

学硕统考专业

1956年，苏共二十大后，匈牙利大党员和群众强烈要求克服个人崇拜，扩大民主，实行经济改革，一些由知识分子、大学生和干部组成的社团组织纷纷成立，其中最有影响者是()。

夏王朝建立后，将其领土划分为九州，派九牧进行治理，在九州范围内根据土地的肥沃程度缴纳贡赋，称为()。

匈牙利社会主义革命中，之所以能顺利建立苏维埃社会主义共和国的主要原因是()。

“我不想变成上帝，或居住在永恒之中，或者把天地抱在怀里，属于人的那种光荣对我就够了。我自己是凡人，我只要求凡人的幸福。”这句话体现的思想是()

詹天佑自主设计修建了中国第一条铁路是在()。

周王室的两大官僚系统是()。

在明朝中叶，农业生产发生了一件非常重要的事件——()，对于当时的食物结构产生了重大的影响

北宋在统一南方割据势力的过程中特设()，把征南所得的财富统一存放，以作日后恢复幽燕之费。

下列描述中，属于冯.诺依曼体系结构的特点是()。①采用流水线技术；②指令和数据均以二进制表示；③存储程序并且存储时不区别数据和指令。

投标报价应考虑风险费，正确的说法是(　　)。

按照《公司法》的规定，以工业产权、非专利技术作价出资的金额不得超过公司注册资本的()。

甲县公安机关(或其工作人员)的下列行为违反《刑事诉讼法》的是()。

奴隶制国家是人类历史上出现最早的国家类型。在公元前40世纪形成的埃及王国，公元前30世纪在幼发拉底河和底格里斯河流域形成的苏美尔、巴比伦、亚述国家。中国最早的奴隶制国家是()。

第一次将几何、天文、算术列为必须学习的科目，并且认为学习这些学科的目的在于实用，而不在于纯理论的思辨的人是()。

常識のある大人なら、目上の人に対して失礼なことを言う________。

SixSecretsofHigh-EnergyPeopleA)There’sanenergycrisisinAmerica,andithasnothingtodowithfossilfuels.Millionsof

Themethodformakingbeerhaschangedovertime.Hops(啤酒花),forexample,whichgivemanyamodembeeritsbitterflavor,are

计算机408

学硕统考专业

1956年，苏共二十大后，匈牙利大党员和群众强烈要求克服个人崇拜，扩大民主，实行经济改革，一些由知识分子、大学生和干部组成的社团组织纷纷成立，其中最有影响者是()。

夏王朝建立后，将其领土划分为九州，派九牧进行治理，在九州范围内根据土地的肥沃程度缴纳贡赋，称为()。

匈牙利社会主义革命中，之所以能顺利建立苏维埃社会主义共和国的主要原因是()。

“我不想变成上帝，或居住在永恒之中，或者把天地抱在怀里，属于人的那种光荣对我就够了。我自己是凡人，我只要求凡人的幸福。”这句话体现的思想是()

詹天佑自主设计修建了中国第一条铁路是在()。

周王室的两大官僚系统是()。

在明朝中叶，农业生产发生了一件非常重要的事件——()，对于当时的食物结构产生了重大的影响

北宋在统一南方割据势力的过程中特设()，把征南所得的财富统一存放，以作日后恢复幽燕之费。

下列描述中，属于冯.诺依曼体系结构的特点是()。①采用流水线技术；②指令和数据均以二进制表示；③存储程序并且存储时不区别数据和指令。

投标报价应考虑风险费，正确的说法是( )。

按照《公司法》的规定，以工业产权、非专利技术作价出资的金额不得超过公司注册资本的()。

甲县公安机关(或其工作人员)的下列行为违反《刑事诉讼法》的是()。

奴隶制国家是人类历史上出现最早的国家类型。在公元前40世纪形成的埃及王国，公元前30世纪在幼发拉底河和底格里斯河流域形成的苏美尔、巴比伦、亚述国家。中国最早的奴隶制国家是()。

第一次将几何、天文、算术列为必须学习的科目，并且认为学习这些学科的目的在于实用，而不在于纯理论的思辨的人是()。

常識のある大人なら、目上の人に対して失礼なことを言う________。

SixSecretsofHigh-EnergyPeopleA)There’sanenergycrisisinAmerica,andithasnothingtodowithfossilfuels.Millionsof

Themethodformakingbeerhaschangedovertime.Hops(啤酒花),forexample,whichgivemanyamodembeeritsbitterflavor,are

投标报价应考虑风险费，正确的说法是(　　)。