Question

连通图的最小生成树是不是唯一的？

如题！
http://hi.baidu.com/mimicekoo/album/item/5c64400fe6dc153f6059f307.html
帮我看看。。谢谢了！

Answer 1

视情况而定，有的是唯一的，有的不是唯一的，所以可以回答不是唯一的。你最好补充个例题，我给你分析一下。
你给的图有三种最小生成树,我不会画图，我把每个图包括的边给出来，你自己画一下吧：1.<a,c>;<a,b>;<b,d>;<d,g>;<d,h>;<e,f>;<f,g>
2.<a,c>;<a,b>;<c,d>;<d,g>;<d,h>;<e,f>;<f,g>
3.<a,c>;<a,b>;<c,h>;<d,g>;<d,h>;<e,f>;<f,g>

发一个最小生成树算法：
最小生成树Prim算法2006-10-21 14:51对于网络，其生成树中的边也带权，将生成树各边的权值总和称为生成树的权，并将权值最小的生成树称为最小生成树（Minimun Spanning Tree），简称为MST。
Prim算法的基本思想是：

(1) 在图G=(V, E) （V表示顶点 ，E表示边）中，从集合V中任取一个顶点（例如取顶点v0）放入集合 U中，这时 U={v0}，集合T(E)为空。

(2) 从v0出发寻找与U中顶点相邻（另一顶点在V中）权值最小的边的另一顶点v1，并使v1加入U。即U={v0,v1 }，同时将该边加入集合T(E)中。

(3) 重复(2)，直到U = V为止。

这时T(E)中有n-1条边，T = (U, T(E))就是一棵最小生成树。

Answer 2

不是唯一的，但是不同的最小部分树的各枝加起来的总和是相等的，因此这也不失为一种检验你对错的办法。