数据结构最小生成树可以重复连接吗?
我这里不能传图片,那我就举个简单例子吧~例如:有一个三角形,三个角为ABCAB=1AC=2BC=2先不论这个三角形是否成立,我要问的是,这个最小生成树是先连接AB,然后B...
我这里不能传图片,那我就举个简单例子吧~
例如:有一个三角形,三个角为ABC
AB=1 AC=2 BC=2
先不论这个三角形是否成立,我要问的是,这个最小生成树是先连接AB,然后BC对吧?那问题来了,是否还要连接AC?因为AC=2 按照最小生成树的定义,要走最近的路径,那么不连接AC的话,从A到c的距离就从2变成AB+BC=1+2=3了,这不就与定义相违背了吗?我想问的最重要一点就是可以这种相互连接吗? 展开
例如:有一个三角形,三个角为ABC
AB=1 AC=2 BC=2
先不论这个三角形是否成立,我要问的是,这个最小生成树是先连接AB,然后BC对吧?那问题来了,是否还要连接AC?因为AC=2 按照最小生成树的定义,要走最近的路径,那么不连接AC的话,从A到c的距离就从2变成AB+BC=1+2=3了,这不就与定义相违背了吗?我想问的最重要一点就是可以这种相互连接吗? 展开
3个回答
展开全部
你理解错了,首先树必须是连通图并且无环,最小生成树也是树的一个特例,那么它也应该符合树的定义,如果你把AC也连起来的话,就生成了一个环。。。
另外一点,所谓的最小路径,是指树的全路径(简单的说,就是所有边的权值之和,假如你连了AB和AC,那么它的全路径是1+2=3),而不是从某点到某点的路径。。。
在此题中,首先连AB,因为它的权值最小,接下来,由于AC与BC的权值相同,所以,你可以连AC,也可以连BC,但只能连其中的一个~~
还有不明白的话,请继续追问~~
另外一点,所谓的最小路径,是指树的全路径(简单的说,就是所有边的权值之和,假如你连了AB和AC,那么它的全路径是1+2=3),而不是从某点到某点的路径。。。
在此题中,首先连AB,因为它的权值最小,接下来,由于AC与BC的权值相同,所以,你可以连AC,也可以连BC,但只能连其中的一个~~
还有不明白的话,请继续追问~~
展开全部
最小生成树.是这样定义的.你要确定你真的理解了.
一个树,包含图中所有顶点,无环,且总的权值最小.
这样的树,是最小生成树.
顺便说下,如果对算法有兴趣,可以看下我的博客.里面有两种最小生成树的算法,我自己写的,希望你能借鉴下.
http://blog.csdn.net/Golden_Shadow
一个树,包含图中所有顶点,无环,且总的权值最小.
这样的树,是最小生成树.
顺便说下,如果对算法有兴趣,可以看下我的博客.里面有两种最小生成树的算法,我自己写的,希望你能借鉴下.
http://blog.csdn.net/Golden_Shadow
已赞过
已踩过<
评论
收起
你对这个回答的评价是?
展开全部
最小生成树中不能有回路
已赞过
已踩过<
评论
收起
你对这个回答的评价是?
推荐律师服务:
若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询