13.用Prim算法和Kruskal算法构造图的最小生成树,所得到的最小生成树是否相同?

一夫多妻 1年前 已收到1个回答 举报

pplroy 春芽

共回答了14个问题采纳率:92.9% 举报

如果原来的图里面任何两条边长都不相同,那么最小生成树是唯一的,此时不管用什么方法算出来的都是一样的
但是如果图里有相等的边,那么最小生成树可能会不唯一,这样就无法保证不同的方法得到同一棵树(即使是同一个算法,只要图的编号方式改变也可能得到不同的最小生成树)

1年前

3
可能相似的问题
Copyright © 2024 YULUCN.COM - 雨露学习互助 - 16 q. 0.019 s. - webmaster@yulucn.com