何时为Prim算法分别使用数组和优先级队列？

Question

这是一个旧的考试问题。

在什么条件下（V，E），我们应该实现使用阵列（由顶点索引）的Prim的 算法的最小优先级的队列，而不是一个堆（具有对数时间两者提取物 - 的 实现最小和减少 - 关键操作）？

在（V，E）的什么条件下，我们应该使用有序数组实现Prim的 算法的最小优先级队列？

Answer 1

当E很大时，最好使用堆作为优先级队列，因为我们将在队列中有许多节点。从数组O（n）/ O（n）中找到最小/最小值min需要时间，而堆只需要O（1）/ log（n）。

如果E很小，我们将在队列中有很少的节点，因此，在这种情况下查找min并将其从数组中移除并不需要很多操作。在这种情况下，使用堆不是必需的，由于构建堆所需的操作，它甚至可能比数组慢。

Answer 2

Prim在二进制堆实现中运行于O（mlog（n））时间，m是边的数量，n是顶点数。然而，当一个图非常密集时，m非常大，那么Prim在O（n^2log（n））中运行。您可以创建一个包含大量（n个）顶点的图形，并将所有顶点连接到彼此以说服您自己。所以......（n-1）+（n-2）+（n-3）......（n-n + 1）。

这可以被重新写为

N（N + 1）/ 2，其为O（n^2）作为记录上

优先级队列数组实现运行在O（N^2）时间这是维基百科页面记录在这里，虽然我没有证据。

因此，当m很大时最好使用邻接矩阵。

你问了一个条件，我会说什么时候m非常大，与n的顺序相同。