Log In
1 vote
For prim's algorithm array implementation takes $O(V^2)$ while min heap implementation takes $O((E+V)\log V)$ time. For dense graph $E = O(V^2).$

So is array implementation considered better or the min heap one???

Does the min heap implementation run better for graph with less edges??
in Algorithms
edited by

1 Answer

2 votes
Best answer
For dense graph $E=O(V^2)$

Prim's Algorithm with Min heap takes $O((E+V)\log V)$ time

Array implementation takes $O(V^2)$

So, for dense graph

Min heap takes $O((V^2+V)\log V) = O(V^2 \log V)$ which is asymptotically more than $O(V^2)$

For sparse graphs, $E = O(V)$ and the time complexities for binary heap and array implementations will be $O(V \log V)$ and $O(V^2)$ respectively.

 So, heap implementation is suitable for sparse graphs and array implementation for dense graphs.

selected by

Related questions

3 votes
1 answer
Explain Prims Algorithm Analysis Of Time Complexity How does $\mathcal{O}(VlogV + ElogV)=\mathcal{O}(ElogV)$
asked Sep 22, 2017 in Algorithms pC 1.7k views
2 votes
0 answers
I have seen many varients of complexities using diferent data structures in implementing Prims Agorithm. Can you pls post standard algorithm and tells me in details how to derive the complexities. Please also mention the variations possibles when data structure changes and How will effect the complexity taking Best case and Worst case senarios .
asked Dec 18, 2016 in Algorithms PEKKA 639 views
2 votes
0 answers
Consider the following graph and Assume node ‘P’ as the starting vertex for Prim’s algorithm. Which of the following can be the correct order of edges to which they are added to construct Minimum Spanning Tree (MST)? P-Q, Q-R, R-W, R-S, V-X, V-U, W-V, S-T P-Q, Q-R, R-W, W-V, V-X, V-U, R-S, S-T P-Q, P-X, X-V, V-U, U-R, R-S, R-W, S-T P-Q, P-X, X-V, V-U, U-R, R-W, R-S, S-T PLEASE EXPLAIN.
asked Jan 8, 2018 in Algorithms ankit_thawal 609 views