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

admin2014-04-17 34

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

相关试题推荐

随机试题

最新回复(0)