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

发布网友发布时间：2022-06-28 21:21

共3个回答

热心网友时间：2023-10-10 16:20

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

热心网友时间：2023-10-10 16:21

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

热心网友时间：2023-10-10 16:21

最小生成树中不能有回路