标签: prims-algorithm

我想知道什么时候应该使用Prim的算法,什么时候Kruskal才能找到最小的生成树？它们都具有简单的逻辑,同样最坏的情况,唯一的区别是实现可能涉及一些不同的数据结构.那么决定因素是什么？

Dijkstra和Prim的算法之间的确切区别是什么？我知道Prim会给MST,但是Dijkstra生成的树也是MST.那究竟是什么区别？

我知道Prim的算法,我知道它的实现,但我总是跳过一个我想问的部分.有人写道,Prim与Fibonacci堆的算法实现是O(E + V log(V)),我的问题是:

• 什么是斐波纳契堆？
• 它是如何实现的？和
• 如何用Fibonacci堆实现Prim的算法？

Prim和Kruskal的算法用于查找连接和无向图的最小生成树.为什么它们不能用于指向的图形？

我这样定义unordered_map:

std::unordered_map<std::string, Edge> edges;

有没有一种从unordered_map边缘中选择随机Edge的有效方法？

我正在研究Prim的算法.代码中有一个部分,切割的下一个顶点将会到达属于该顶点的顶点集MST.在这样做的同时,我们还必须"更新另一组中与离开顶点相邻的所有顶点".这是来自的快照CLRS:

有趣的部分在于行号.11.但是由于我们在这里使用堆,我们只能访问最小元素right(heap[0])？那么我们如何从堆中搜索和更新顶点,即使它们不是最小的顶点,因此除了线性搜索之外我们知道它们在哪里？

任何人都可以请给出这两种算法的一些应用程序,它们可以用于哪些应用程序？

我正在查看Prim算法的维基百科条目,我注意到它的邻接矩阵的时间复杂度是O(V ^ 2),它的堆和邻接列表的时间复杂度是O(E lg(V))其中E是边数和V是图中顶点的数量.

由于Prim的算法用于更密集的图,因此E可以接近V ^ 2,但是当它接近时,堆的时间复杂度变为O(V ^ 2 lg(V)),其大于O(V ^ 2).显然,堆只会在搜索数组时提高性能,但时间复杂性则另有说法.

算法如何通过改进实际减速？

我发现普里姆算法的时间复杂度为到处O((V + E)登录V)= E日志V.但是我们可以看到算法:

似乎时间复杂度为O(V(log V + E log V)).但如果其时间复杂度为O((V + E)log V).那么嵌套必须是这样的:

但上面的嵌套似乎是错误的.

我试图理解为什么Prim和Kruskal在稀疏和密集的图形方面有不同的时间复杂性.在使用几个小程序来演示每个小程序如何工作之后,我仍然对图的密度如何影响算法感到困惑.我希望有人能给我一个正确方向的推动.