连通图的最小生成树是不是唯一的?如题!http://hi.baidu.com/mimicekoo/album/item/5c64400fe6dc153f6059f307.html帮我看看.谢谢了!
来源:学生作业帮助网 编辑:作业帮 时间:2024/07/03 14:00:35
![连通图的最小生成树是不是唯一的?如题!http://hi.baidu.com/mimicekoo/album/item/5c64400fe6dc153f6059f307.html帮我看看.谢谢了!](/uploads/image/z/8520564-12-4.jpg?t=%E8%BF%9E%E9%80%9A%E5%9B%BE%E7%9A%84%E6%9C%80%E5%B0%8F%E7%94%9F%E6%88%90%E6%A0%91%E6%98%AF%E4%B8%8D%E6%98%AF%E5%94%AF%E4%B8%80%E7%9A%84%3F%E5%A6%82%E9%A2%98%21http%3A%2F%2Fhi.baidu.com%2Fmimicekoo%2Falbum%2Fitem%2F5c64400fe6dc153f6059f307.html%E5%B8%AE%E6%88%91%E7%9C%8B%E7%9C%8B.%E8%B0%A2%E8%B0%A2%E4%BA%86%21)
连通图的最小生成树是不是唯一的?如题!http://hi.baidu.com/mimicekoo/album/item/5c64400fe6dc153f6059f307.html帮我看看.谢谢了!
连通图的最小生成树是不是唯一的?
如题!
http://hi.baidu.com/mimicekoo/album/item/5c64400fe6dc153f6059f307.html
帮我看看.谢谢了!
连通图的最小生成树是不是唯一的?如题!http://hi.baidu.com/mimicekoo/album/item/5c64400fe6dc153f6059f307.html帮我看看.谢谢了!
视情况而定,有的是唯一的,有的不是唯一的,所以可以回答不是唯一的.你最好补充个例题,我给你分析一下.
你给的图有三种最小生成树,我不会画图,我把每个图包括的边给出来,你自己画一下吧:1.;;;;;;
2.;;;;;;
3.;;;;;;
发一个最小生成树算法:
最小生成树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))就是一棵最小生成树.