Question

数据结构最小生成树可以重复连接吗？

我这里不能传图片，那我就举个简单例子吧~
例如：有一个三角形，三个角为ABC
AB=1 AC=2 BC=2
先不论这个三角形是否成立，我要问的是，这个最小生成树是先连接AB，然后BC对吧？那问题来了，是否还要连接AC？因为AC=2 按照最小生成树的定义，要走最近的路径，那么不连接AC的话，从A到c的距离就从2变成AB+BC=1+2=3了，这不就与定义相违背了吗？我想问的最重要一点就是可以这种相互连接吗？

Answer 1

你理解错了，首先树必须是连通图并且无环，最小生成树也是树的一个特例，那么它也应该符合树的定义，如果你把AC也连起来的话，就生成了一个环。。。
另外一点，所谓的最小路径，是指树的全路径（简单的说，就是所有边的权值之和，假如你连了AB和AC，那么它的全路径是1+2=3），而不是从某点到某点的路径。。。
在此题中，首先连AB，因为它的权值最小，接下来，由于AC与BC的权值相同，所以，你可以连AC，也可以连BC，但只能连其中的一个~~
还有不明白的话，请继续追问~~

Answer 2

最小生成树.是这样定义的.你要确定你真的理解了.
一个树,包含图中所有顶点,无环,且总的权值最小.
这样的树,是最小生成树.
顺便说下,如果对算法有兴趣,可以看下我的博客.里面有两种最小生成树的算法,我自己写的,希望你能借鉴下.
http://blog.csdn.net/Golden_Shadow

Answer 3

最小生成树中不能有回路