有人提出这样的一种从图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)),这样构成回路,就不能求得最小生成树了。

【答案解析】