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

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

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

计算机408

学硕统考专业

相关试题推荐
随机试题
最新回复(0)