Prim算法的最坏情况图

Question

我的算法类正在讨论Prim算法，作为查找加权图的最小生成树的方法。我们的教授让我们试着想一个Prim算法需要N^2次解决的图的例子（N =顶点数）。班上没有人能够想到他们的头顶，所以我问你。我很确定Prim的算法= O（N^2），所以这将是算法的最坏情况。

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

Answer 1

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

如果图形完整，则有O(N^2)边缘，因此只需读取图形即可获得O(N^2)。