Prim 算法的最坏情况图

Question

我的算法类正在谈论prim的算法，作为查找加权图的最小生成树的一种方法。我们的教授要求我们尝试考虑一个图的示例，即Prim的算法需要n^2时间来解决(n =顶点数(。班上没有人能想到他们的头顶，所以我问你。我很确定Prim的算法= O(n^2(，所以这将是算法的最坏情况。

图形需要n^2时间才能解决prim的算法的一个好示例？

Answer 1

如果我正确理解您的问题，则示例很琐碎。

如果图形完成，则需要O(N^2)边缘，因此仅阅读图是O(N^2)。