Cormen 23.2-3

1 vote
313 views
For a sparse graph $G=(V,E)$ where $|E|=\Theta (V)$ is the implementation of Prim’s algorithm with a Fibonacci heap asymptotically faster than the binary-heap implementation? What about for a dense graph, where $|E|=\Theta (V)^{2}$? How must the sizes $|E|$ and $|V|$ be related for the Fibonacci-heap implementation to be asymptotically faster than the binary-heap implementation?

__________________________________________________________________________

Plz tell me difference between Sparse and Dense graph here? How Dense graph implemented and how it make difference for this question
0
0

the first link you provided for

difference btw array implementation and heap implementation

but your question contains Fibonacci heap and binary heap.

i got one doubt in that same question, Arjun sir mentioned that (V2 . log V) is asymptotically equal, how they are equal?

0
@shaik same doubt
0
Time complexity of prims algorithm when binary heap is used is $O(ElogV)$

Time complexity of prims algorithm when fibonacci heap is used is $O(E + VlogV)$

Now, for a sparse graph(where the number of edges are of the order of number of vertices i.e. $E=\theta(V)$, then time complexity becomes

$O(VlogV)$ for binary heap and

$O(V + VlogV)=O(VlogV)$ for fibonacci heap

For a dense graph (where edges might exist in every two vertices i.e. near to $\frac{V(V-1)}{2}$ which is $O(V^2)$ i.e. $E=O(V^2)$), the time complexity becomes,

$O(V^2logV)$ for binary heap and

$O(V^2+VlogV) = O(V^2)$ for fibonacci heap.
2
@Shaik That was wrong - corrected now.
0
@Arjun Sir

How fibonacci heap implemented?
0

Fibonacci heap is Advanced Data Structure, it is not in GATE syllabus.. but on our own interest we can learn it

Related questions

1
1.2k views
Suppose that edge weights are uniformly distributed over half open interval $[0,1)$. Which algorithm kruskal's or prim's can make you run faster?