algorithm - Prim 算法和 MST

Question

我如何描述一组具有 V 顶点和 E 边的图，其中确认 Prim 算法的优先级队列实现的最坏情况运行？

Answer 1

好吧，如果不知道具体的实现是什么样子很难说，但如果我没记错的话，你总是需要在确定 MST 时检查 Θ(E) 边缘。如果优先级队列实现为二进制堆（这是标准方式），那么每个“检查”都是 O(log V)，所以 O(E * log V) 的最坏情况运行时间总是发生。