search
Log In
2 votes
267 views
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 :

• O(V) initialization.

• O(V · time for EXTRACT-MIN).

• O(E · time for DECREASE-KEY).

If the edges are in the range 1, . . . , |V| the Van Emde Boas priority queue can speed up EXTRACT- MIN and DECREASE-KEY to O(lg lg V) thus yielding a total running time of O(V lg lg V +E lg lg V) = O(E lg lg V ). If the edges are in the range from 1 to W we can implement the queue as an array [1...W+1] where the ith slot holds a doubly linked list of the edges with weight i. The (W+1)st slot contains ∞. EXTRACT-MIN now runs in O(W) = O(1) time since we can simply scan for the first nonempty slot and return the first element of that list. DECREASE-KEY runs in O(1) time as well since it can be implemented by moving an element from one slot to another.

Doubt 1 : Incase of range 1, . . . , |V| , how EXTRACT- MIN and DECREASE-KEY speed up to O(lg lg V).

Doubt 2 : why doubly linked list is used for range 1.... |W| ??
in Algorithms 267 views
0

Note that, in any case, the algorithm performs O(1) work and then possibly recurses on a subtree over a universe of size M1/2 (an m/2 bit universe). This gives a recurrence for the running time of T(m)=T(m/2) + O(1), which resolves to O(log m) = O(log log M).

 

i.e. ans for 1st query

ok?? 

0
Superb question

1 Answer

3 votes
 
Best answer

for clarification of your 1st doubt, you can read https://en.wikipedia.org/wiki/Van_Emde_Boas_tree

 

for 2nd doubt, i hope there is no need to use doubly linked list

 array [1...W+1]  ===> already array is sorted by edge weights

where ith slot holds a doubly linked list of the edges with weight i. 

let assume there are 5 edges with weight 15,

they use double linked list due to efficiently usage, if you use single linked list, after extracting one edge from it, you need to update it's previous node, next pointer. ( but no problem with using singly linked list )
 

but when you decrease the key, let the 3rd edge in weight 15,....

it need to update 2nd edge next pointer, array element points to new edge ( but no problem with using singly linked list )

 

 


selected by
0
doubly linked list is better

right?

because find next and find prev two things need here
0
yes mam, using double linked list is better but not mandatory

Related questions

2 votes
1 answer
1
1 vote
0 answers
2
199 views
For a sparse graph $G=(V,E)$ where $|E|=\Theta (V)$ ... Plz tell me difference between Sparse and Dense graph here? How Dense graph implemented and how it make difference for this question
asked Aug 24, 2018 in Algorithms srestha 199 views
1 vote
0 answers
3
306 views
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 306 views
1 vote
0 answers
4
383 views
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 383 views
...