当恰好有两条权值相同的边时，你要选择那条，这样就会出现不同的生成树。

是唯一的！
因为我昨天刚发现有一道题目让证明这个结论。
到底如何证啊？这问题困扰我好久了。

小弟来解吧，
吹一点，很简单的。
简单连通图。意思就是
如
A----------B
|          |
|          |
C----------D
从任一点出好，能够通过深度优先和广度优先遍历所有结点。例子，从A点出发，深度的，就是ABDC所有结点都访问过了，就是简单连通图了。
所以最小生成树也就是唯一的了。

斑竹，我还是每听懂你说的意思啊？你说的深度优先遍历没有涉及权值啊？

我有了个想法：
假定存在两棵不同的最小生成树A，B
对于两棵树A和B中任意相同点对（i,j）
一定是下面的情况：
1.A中有边相连，B中也有边相连，此时这两点之间的边一定是同一条（因为没有多重边）
2.A中无边相连，B中也无边相连
3.A中有边相连，B中无边相连
4.A中无边相连，B中有边相连

因为两棵树不同，所以3或者4的情况必然至少出现一次
（如果只是1，和2，那么两棵树就完全一样了）
假设存在点对（v,w）属于情况3，（4类似）
那么我们将A中点对（v,w）间的边e加到B中，
B中会形成唯一的一条包含边e的回路。
可以肯定e一定不是这个回路中权值最大的边，
（在各边权值都不等的情况下，回路中权值最大的边不会出现在任意一个最小生成树中）   ！！！ 有定理支持


显然A这棵最小生成树包含e,所以如果e的权值最大就会出现矛盾。
那么我们从B中形成的这个回路中去掉一个权值最大的边（一定不是e）
就会得到另一颗树C，显然树C的权值比最小生成树树B要小。
（因为去掉边的权值要比加入边e的权值大）

这就与B是最小生成树矛盾。

言之有理.

唯一