Worst-Case Graph for Prim's Algorithm

0
votes

My Algorithms class is talking about Prim's Algorithm as a method of finding Minimum Spanning Trees of weighted graphs. Our professor asked us to try to think of an example of a graph that Prim's Algorithm takes N^2 time to solve (N = number of Vertices). No one in the class could think of one off the top of their head, so I'm asking you. I'm pretty sure Prim's Algorithm = O(N^2), so this would be the worst-case scenario for the algorithm.

What's a good example of a graph that takes N^2 time for Prim's Algorithm to solve?

1
algorithmgraphminimum-spanning-treeprims-algorithm
If the graph is complete, there're O(N^2) edges, so just reading the graph is O(N^2). - kraskevich

1 Answers

2
votes

If I understand your question correctly, the example is trivial.

If the graph is complete, there're O(N^2) edges, so just reading the graph is O(N^2).