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

admin2014-04-17 44

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

选项

答案此方法不能求得最小生成树。例如，对于图7-8a所示的带权连通无向图，按照上述方法从顶点0开始求得的结果为图7-8b所示的树，显然它不是最小生成树，正确的最小生成树如图7—8c所示。在有些情况下，上述方法甚至无法求得最小生成树。

解析

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

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

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

计算机408

学硕统考专业

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

李鸿章奏请在天津设立的北洋水师学堂的落成时间是()。

中共十六届五中全会提出，建设社会主义新农村的要求是生产发展和()。

1895年发现X射线，拉开物理学革命序幕的科学家是()。

隋唐时期陆路交通线和海路交通线都可到达的地区是()

下列现象均属于明朝手工业进步的表现的是()①嘉万年间民营手工业渐居主要地位②匠役制度瓦解③出现了雇佣劳动、组织手工工场的经营方式④加强了对工匠的剥削，工匠的人身依附关系加强

玛雅人的金字塔主要功能是()。

隋朝建立了三省六部制，其中负责审议的部门是()。

某机字长32位，主存容量32MB，按字节编址；该机的Cache采用4路组相联映射方式，Cache容量为16KB，块长为4个字，试回答下列问题：(1)主存地址位数为多少?(2)画出主存地址格式示意图，注明各字段名称及位数。(3)设该Ca

若无向图G=(V,E)中含有7个顶点，要保证图G在任何情况下都是连通的，则需要的边数最少是____。

杜甫的诗集中反映了唐王朝由盛转衰的重大事件，号称“诗史”。()

掌握传染病潜伏期的意义在于

慢性阿米巴痢疾的临床表现是

下述情形中，不属于国家、集体医疗机构中的医师在执业活动中享有的权利的是

可有痉挛性斜颈表现的病是

有利于焊前排气；排渣，减少气孔、夹渣，提高焊缝质量的处理方法为(　　)。

简述教学目标的含义及其意义。

在微机的硬件设备中，有一种设备在程序设计中既可以当做输出设备，又可以当做输入设备，这种设备是（）。

Iamgoingtoattendtheconference,butyou_______withme.

计算机408

学硕统考专业

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

李鸿章奏请在天津设立的北洋水师学堂的落成时间是()。

中共十六届五中全会提出，建设社会主义新农村的要求是生产发展和()。

1895年发现X射线，拉开物理学革命序幕的科学家是()。

隋唐时期陆路交通线和海路交通线都可到达的地区是()

下列现象均属于明朝手工业进步的表现的是()①嘉万年间民营手工业渐居主要地位②匠役制度瓦解③出现了雇佣劳动、组织手工工场的经营方式④加强了对工匠的剥削，工匠的人身依附关系加强

玛雅人的金字塔主要功能是()。

隋朝建立了三省六部制，其中负责审议的部门是()。

某机字长32位，主存容量32MB，按字节编址；该机的Cache采用4路组相联映射方式，Cache容量为16KB，块长为4个字，试回答下列问题：(1)主存地址位数为多少?(2)画出主存地址格式示意图，注明各字段名称及位数。(3)设该Ca

若无向图G=(V,E)中含有7个顶点，要保证图G在任何情况下都是连通的，则需要的边数最少是____。

杜甫的诗集中反映了唐王朝由盛转衰的重大事件，号称“诗史”。()

掌握传染病潜伏期的意义在于

慢性阿米巴痢疾的临床表现是

下述情形中，不属于国家、集体医疗机构中的医师在执业活动中享有的权利的是

可有痉挛性斜颈表现的病是

有利于焊前排气；排渣，减少气孔、夹渣，提高焊缝质量的处理方法为( )。

简述教学目标的含义及其意义。

在微机的硬件设备中，有一种设备在程序设计中既可以当做输出设备，又可以当做输入设备，这种设备是（）。

Iamgoingtoattendtheconference,butyou_______withme.

有利于焊前排气；排渣，减少气孔、夹渣，提高焊缝质量的处理方法为(　　)。