GESP 2024年3月 C++八级判断题第6题

Question

求 v 顶点 e 边带权连通无向图的最小生成树，Prim 算法的时间复杂度为 O(v×e)。

Accepted Answer

答案：错误（×）。错误。朴素 Prim 为 O(v²)，二叉堆优化为 O(e·log v)，并不存在 O(v×e) 这一标准结论。

GESP 2024年3月 C++八级 判断题 第6题