Cormen 23.2-3

Question

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

Comments

https://gateoverflow.in/20172/array-implementation-better-the-heap-case-prims-algorithm

https://stackoverflow.com/questions/12599143/what-is-the-distinction-between-sparse-and-dense-graphs

---

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 (V² . log V) is asymptotically equal, how they are equal?

 

---

@shaik same doubt

---

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.

---

@Shaik That was wrong - corrected now.

---

@Arjun Sir

How fibonacci heap implemented?

---

@srestha

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