为什么Kruskal和Prim MST算法对稀疏和密集图有不同的运行时？
为什么Kruskal和Prim MST算法对稀疏和密集图有不同的运行时？
提问于 2010-01-06 16:45:55
我试图理解为什么Prim和Kruskal在处理稀疏和密集图时具有不同的时间复杂性。在使用了几个演示如何工作的applet之后，我仍然对图的密度如何影响算法感到有点困惑。我希望有人能给我一个正确的方向。
Stack Overflow用户
发布于 2010-01-07 03:53:20
Cormen等人的算法确实给出了分析，在这两种情况下都使用了图的稀疏表示。使用Kruskal的算法(在不相交的组件中链接顶点，直到一切都连接起来)，第一步是对图的边进行排序，这需要O(E，lg，E)，并且他们简单地确定没有比这更长的时间了。使用Prim的算法(通过添加当前树上尚未添加的最近顶点来扩展当前树)，他们使用斐波那契堆来存储挂起顶点的队列，并获得O(E +V lgV)，因为使用斐波那契树减少到队列中顶点的距离仅为O(1)，并且每个边至多执行一次。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/2011753
复制相关文章
相似问题
腾讯云开发者
