Prims algo graph

#1

what is the time complexity of prims algo??

#2

hello @shampblocks

assuming u r using min heap
The time complexity of the Prim’s Algorithm is O ( ( V + E ) l o g V ) because each vertex is inserted in the priority queue only once and insertion in priority queue take logarithmic time

#3

But how we are sure that maximum size of heap will be V??

#4

v is the number of vertex, in worst case heap can have all vertex.

example->
all nodes are directly connected to source node

#5

And how each vertex inserted once?? It may be inserted more than once?? Because in later stage may be from some other vertex it will be added and it has smaller edge value…??

#6

no , pls recheck the prims algorithm.

#7

As in prims algo we start from any vertex and put the edges connected to it in heap… So when let say we started with 0 and neighbour of 0 are 1 2 and 3 so we insert 0,1 0,2 0,3 and take minimum edge in next iteration… Let say in next iteration 2 has less weight but 2 is also connect to 1 so we add one more instance of 2 ?? Is i m correct??

#8

Sorry 2 is connected to 3*

#9

Then in heap 3 has two instances??

#10

ok think it using set.
point a ) in each step distance of one node will be assigned permanently

point b) now to update its neighbor in worst case we will have neighbours E. using set we can delete their previous entry ElogV + update new entry ElogV

now using this we can say that size will never exceed V.

#11

Yess size part I understood but total number of insertion +deletion should be mlogV where m should E in this way I thought… One element insert in one time that i was not getting… Is this correct??

#12

And in every step before inserting we should check that there is any instance of that element… To make sure that size not exceed V??

#13

E is number of edges.
in worst case my node can be connected to all other nodes. so in that case there will be E neighors and therfore ElogV updation

#14

Please clear it sir??

#15

yeah i have already mentioned na.

while iterating to neighbours of current node. we will check whether they exist in set or not .
if they exist and their current value is less than the value we r going to assing then we delete it and insert the new value.

otherwise if it exist but new value is greter than it current value .
we will do nothing (i,e neither we delete it , neither we insert new value)

otherwise if it is not there in set then we will insert it.

#16

Ohk sir thanks… And i find confusion on finding graph problem time complexity in other problems it’s easy but in graph this E and V confused alot it’s not tough but confusing… How to find it in simpler way??

#17

literally mere pass iska koi jawab nahi hai :sweat_smile:

practice se improve ho jayega

#18

Yess but i saw like in dijektras somewhere mentioned ELogv somewhere E+VlogV somewhere ElogE somewhere (E+v) Loge this type of problem I face

#19

using different method of implementation they derive different time complexity.

#20

I though same but logic and code is same they were using priority queue