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

admin2014-04-17  32

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

选项

答案例如对于图7—8d所示的带权连通无向图,从顶点0出发,找到顶点1(边(0,1)),从顶点1出发,找到顶点3(边(1,3)),再从顶点3出发,找到顶点0(边(3,0)),这样构成回路,就不能求得最小生成树了。 [*]

解析
转载请注明原文地址:https://kaotiyun.com/show/oYxi777K
0

最新回复(0)