algorithm - Prim 算法的最坏情况图

Question

我的算法课正在讨论 Prim 算法作为一种寻找加权图的最小生成树的方法。我们的教授让我们试着想一个图的例子，Prim 的算法需要 N^2 时间来解决(N = 顶点数)。类没有人能凭空想到一个，所以我问你。我很确定 Prim 算法 = O(N^2)，所以这将是该算法的最坏情况。

Prim 算法需要 N^2 时间求解的图的一个很好的例子是什么？

Answer 1

如果我正确理解你的问题，那么这个例子是微不足道的。

如果图是完整的，则有 O(N^2) 条边，因此仅读取图就是 O(N^2)。