edited by
1,919 views
1 votes
1 votes
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??
edited by

1 Answer

Best answer
3 votes
3 votes
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

0 votes
0 votes
1 answer
1
anonymous asked Jun 26, 2016
640 views
2 votes
2 votes
2 answers
3
techbrk3 asked Nov 16, 2017
495 views
(a,b),(b,c),(a,d),(e,f),(d,g),(c,e)(g,f),(f,c),(g,d),(c,e),(d,b),(d,a)(c,f),(c,e),(e,d),(a,b),(d,g),(b,c)None of the above
3 votes
3 votes
1 answer
4
pC asked Sep 22, 2017
2,506 views
Explain Prims AlgorithmAnalysis Of Time ComplexityHow does $\mathcal{O}(VlogV + ElogV)=\mathcal{O}(ElogV)$