首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >最小生成树: prim和kruskal

问最小生成树: prim和kruskal
EN

Stack Overflow用户
提问于 2020-02-10 13:04:01
回答 1查看 139关注 0票数 1

对于用于STL优先级队列优化的prim算法和使用c ++排序的kruskal算法,哪种类型的图适合这两种算法?

EN

回答 1

Stack Overflow用户

发布于 2020-04-14 15:49:36

你可能已经知道了,

Prim适用于密集图,Kruskal适用于稀疏图。

对于Kruskal,算法的复杂性主要取决于对边的排序。

因此,在一般情况下,它的大O是O(E log E),具有正常的有效排序。

使用Prim,其复杂度与Dijkstra的算法相似。(您可以轻松地将Dijkstra代码修改为Prim )

因此,它类似于具有优先级队列(堆)的O((V+E) log(V))。

因此,当图是稀疏的(E < V)时,Kruskal是O(E log E),Prim是O(V log V),所以Kruslak赢了。

当图是密集的(E is close to V^2-1)时,Prim是O(V^2 log V^2),Prim是O(V^2 log V),所以Prim获胜。

但在大多数情况下,您可以同时使用这两种算法,而没有明显的差异。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/60144343

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档