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

Question

这是一道古老的考试题。

在 (V, E) 的什么条件下，我们应该使用数组（由顶点索引）而不是堆（Extract-Min 和 Decrease-Key 操作的对数时间实现）来实现 Prim 算法的最小优先级队列)?

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

Answer 1

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 相同的顺序时。

Answer 2

当 E 很大时，最好使用堆作为优先级队列，因为队列中有很多节点。从数组 O(n)/O(n) 中找到 min/remove min 需要时间，而堆只需要 O(1)/log(n)。

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