Log In
1 vote
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
in Algorithms 313 views

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?


@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?


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

Please log in or register to answer this question.

Related questions

2 votes
1 answer
2 votes
1 answer
Suppose that all edge weights in a graph are integers in the range from 1 to |V|. How fast can you make Prim's algorithm run? What if the edge weights are integers in the range from 1 to W for some constant W? Answer given :- The running time of Prims algorithm is composed of : ... - MIN and DECREASE-KEY speed up to O(lg lg V). Doubt 2 : why doubly linked list is used for range 1.... |W| ??
asked Jul 21, 2018 in Algorithms Sandy Sharma 444 views
1 vote
0 answers
suppose that a graph G has MST already computed. How quickly can we update the MST if we add a new vertex and incident edges to it. I know for the best case scenario when a single edge is incident from the newly added vertex. but for the worst case, when ... many edges. This will end up being linear time since we can reuse part of the DFS that we had already computed before detecting each cycle.
asked Aug 19, 2018 in Algorithms aambazinga 419 views
1 vote
0 answers
Here the graph that I was trying to find MST using algo in cormen.(If you need algo to ask, I supposed you have it) Algorithms uses min queue in process, my dobut is when it came to choice b/w vertex 'c' and 'd' as at that time both will have 8 has key ... we get wrong answer, so prism deal with this case? If you need algo I will given you, or just please refer chapter 23 cormen prim's algorithm.
asked Aug 5, 2017 in Algorithms bhuv 467 views