Prim算法的最坏情况图

Question

我的算法类讨论的是Prim算法，它是一种寻找加权图的最小生成树的方法。我们的教授让我们试着想出一个图的例子，Prim的算法需要N^2个时间来求解(N =顶点的数量)。班上没人能想出一个，所以我问你。我非常确定Prim的算法= O(N^2)，所以这将是该算法的最坏情况。

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

Answer 1

如果我没理解错你的问题，这个例子很简单。

如果图是完整的，那么就有O(N^2)边，所以只读图就是O(N^2)。