我想进一步了解prim的时间复杂度的细节。基本上，prim 的时间复杂度是 O(V^2)。当使用二叉堆或斐波那契堆时，时间复杂度提高到O(E + V log(V))或O(Elog(V))。
我的问题如下。
为什么有些代码使用基本的 prim 算法，即使其他版本的 prim 给出了更好的解决方案？使用给出
O(V^2)的基本 prim 算法是否有特殊原因？与高级 prim 版本相比，实现起来非常容易。否则，我假设没有特殊原因使用基本 prim 算法。当给出二分图时，我可以将斐波那契或二叉堆 prim 版本应用于二分图而不是基本 prim 版本吗？我分析过的现有代码在二部图中使用了基本的 prim 算法。我想做的是让代码速度更好。因此，我想使用二进制或斐波那契堆来更改 prim 的数据结构，以减少执行时间。是否可以将高级 prim 版本用于二分图而不是普通图？
最佳答案
当您在现实生活中实现算法时，渐近时间复杂度并不是最重要的:实际效率和简单性也很重要。
首先，尽管使用斐波那契堆的 Prim 算法的理论复杂度优于二叉堆(O(E log V) vs O(E + V log V))，但斐波那契堆在实践中确实很慢，因此您的值(value)E 应该非常大才能注意到差异。我还没有看到这方面的任何实际例子。简单二进制(或 k 进制，k 为 4 或 8)非常非常快。
其次，有稠密图(其中E~V^2)和稀疏图(其中E~V)。 (当然也有中间类别，但一般来说任何实用的图都可以被认为是稀疏的或稠密的)。对于密集图，具有 O(V^2) 运行时间的标准 Prim 算法在理论上和实践上都是最好的。也许这就是使用更简单版本的原因。或者也许性能在那一点上并不重要，因为图表没有那么大。
关于你的第二个问题:我还没有听说过在二分图中找到 MST 的任何特定算法。当然，您可以应用任何版本的算法，但我怀疑是否存在针对二分法的特殊技巧。
附言对于稀疏图，请考虑 Kruskal 算法。它是 O(E log E)，但唯一重的部分是排序，今天也很快。
关于algorithm - 给定二部图时使用斐波那契堆或二叉堆的 prim 算法的时间复杂度，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/47450640/