The Gateway to Computer Science Excellence
+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 by Active (2.5k points)
edited by | 345 views

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.
by Boss (31.4k points)
selected by

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,321 answers
105,145 users