Prim’s Algorithm Minimum Spanning Tree Graph Algorithm

Prim’s Algorithm Minimum Spanning Tree Graph Algorithm


Hello friends my name is Tushar and
today we’re going to talk about how to find minimum spanning tree using Prim’s
algorithm.In another video I talked about how to find minimum spanning trees
using Kruskal’s algorithm and both Prim and Kruskal algorithms are greedy
algorithms. So what is the spanning tree of an undirected
graph? A spanning tree is a subgraph of a graph such that all ‘n’ vertices are
connected to each other and there are total n-1 edges in the subgraph.
So basically there is no cycle in this subgraph.What is a minimum spanning
tree? A minimum spanning tree is a spanning tree of weighted undirected graph such that the sum of
the weight of the edges is minimum. So suppose we have this graph here, here we have 4 vertices A,B,C,D,if we
pick 3, this 3 edges (A,B),(B,C) and (C,D),we get a
minimum spanning tree and the sum of their weights is one 1+1+1,that is
3.For Prim’s algorithm we need a binary heaps which supports decrease key
operation and which also supports contains and find operation. So in the next section let’s quickly
look at this data structure before talking Prim’s tree,prim’s algorithm.
Also if you don’t know what binary heap is I highly recommend you to read about
binary heap before watching this video. Our minimum binary heap or priority queue needs to
support these four operations-extractMin, add,contains and decrease. It,a regular binary heap already
supports extractMin and add in O(logn) time and O(logn) time and we also need
to support contains and decrease on O(1) time and O(logn) time. Let’s see how this works.So if we know
about regular minimum binary tree,we know that value at every node is less
than or equal to both its children. So -1 is less than equal to 2 and 6,2
is less than equal to 4 and 5,6 is less than equal to 7 and 8.So this satisfies all
the properties of minimum binary heap. Also we know that the values of the
minimum binary heap are stored in array. So this is just a logical diagram.In
reality this pair is stored in location 0,this pair is stored in location 1,
location 2,location 3,4,5 and 6. of array.To get the left child we
apply this formula 2i+1.So to get this guy’s left child in the array we replace 0
with ‘i’ so 2×0+1 so that’s 1 so this is left child and 2×0+2 so
this is right child.For 2’s left child we replace ‘i’ with 2 so 2×2+1 so that’s 5 and 2×2+2
so that’s 6 so thats it’s right child and to get a parent,for example to get
4’s parent in array we replace 4 with ‘i’ so (4-1)/2 so that’s 1. So 4’s parent is 1.So this is how
regular binary heap works.Now to support these 2 contains and decrease operation we need another map,we need another data
structure map to do that efficiently and in this map we are going to store this key. So every pair here is identified by this
key,unique value key and the second value here is just used to position them
in this binary heap.So now to check,so the way this map works is the key here
is this key and the value here is the position in the array.So ‘a’ is stored at
location 0, ‘b’ is stored at location 1, ‘c’ is stored at location 2 of array,’d’ is
stored at location 3,’e’ at 4,’f’ at 5 and ‘g’ at 6.So now to support contains operation what we do is we check does this heap
contains ‘c’ so all you have to do is go to this map and check does this map have a key ‘c’ and yes it does. So this can be done in a map in O(1)
time.What about decrease operation. So let’s say we have to decrease the
value of 5 to -2.So decrease this 5 to -2,this ‘F’
to -2.So what we do is we first come to this map,check where this ‘F’ is stored.So
‘F’ is stored at location 5,so we reach this point. Now we change the value here to be ‘F’ and -2.At this point it violates the property
of binary heap,minimum binary heap because this value is less than it’s parent. So using this formula (i-1)/2 so
(5-1)/2 so that’s 2 we,we check if this value is
less than this,it is so we’re gonna swap this data here. So here we get (F,-2) and here we have (C,6) and also
we have to go into this corresponding map and change their locations.So F’s new
location is 2 and C’s new location is 5.Now this ‘F’ is still violating this
property here because – 2 is less than -1 so again we’re gonna do a swap here. So (A,-1) is here and (F,-2) is here. So then,now our F’s new location is 0 and A’s
new location is 2. So this is how we support decrease key
operation in O(logn) time.So hopefully this helps you understand how we’re
going to use these 2 data structures combined together to have these 4
operations in the Prim’s algorithm. So in the next section let’s look at the
Prim’s Algorithm.The way this algorithm work is first we take all the vertices,put in this heap
plus map data structure which we just,just discussed with the value infinity and
the note the vertex from which we’re gonna start as a value 0.In this case we’re
gonna start from ‘A’ but we can start from any vertex.Then we’re gonna
explore neighbors of ‘A’,in this case ‘D’ and ‘B’ and check if they exist in this heap
plus map and if they do and if the value they are attached to is greater
than this edge weight then we update their values.So D,infinity so we update it to
1,A’s value is 3 so we update it to 3 and then we keep repeating this
process,then extractMin again and keep repeating this process until there are
elements in this heap plus map data structure.Also we’re going to store, we’re going to have another map
going from vertex to edge which is going to store for,for every vertex
which edge is contributing to the minimum value in this heap plus map data
structure. This is to get the final result and in
here we’re going to store the final result. So let’s do a traversal on this graph here.So
we start from ‘A’ we do an extract,we do an extractMin here so the minimum value is 0 so ‘A’ so ‘A’ comes
out of this heap plus map data structure. Then we’re going to explore neighbors of
‘A’.So first we go to ‘D’,so ‘D’ contains in this heap plus map and the value attached
with ‘D’ is infinity which is greater than 1 so we update this value to 1.And in
here we’re going to store this,say that ‘D’ is introduced,the minimum value for D
is coming from this edge (A,D).Then we’re gonna explore other neighbor of ‘A’ which is ‘B’.’B’
is in this map here and ‘B’,the minimum value of B is,the value attached with ‘B’ is
infinity which is greater than 3 so this value becomes 3 and we’ll indicate here
that ‘B’ is,B’s minimum value edge is coming from this edge (A,B).So as we
discussed heap plus map,the decrease operation can happen in O(logn)
time and contains operation can happen in O(1) time. So at this point we’ve done exploring all
the neighbours of ‘A’ so we’re done with ‘A’. And then we’re going to do extractMin on
this heap plus map which can again be done in
O(logn) time and get the next value.So the next min here is 1. So we’ll take 1 out and then we’re going to
check which edge contributed to this value 1 and to do that we come here and
see where,which edge contributed to that. So D’s (A,D) edge.So (A,D) will go into this final
result which has all the edges in the minimum spanning tree.Then we’re going
to remove this guy from here,from this heap plus map data structure and explore
its neighbours. So D’s 1st neighbour is 6 and ‘E’ is in
this heap plus map data structure,it is and the value attached to this guy is
greater than 6 so we replace this with 6 and we will say that ‘E’ is coming from (D,E). Then we’re gonna explore another
neighbor of ‘D’. So that’s ‘B’ and the value,’B’ is in
this heap plus map but the value with B is 3 is not less than this value 3 so we’re just going to ignore this edge
here and then we’re gonna look at the next neighbor of ‘D’ which is ‘C’.So ‘C’ is in this
heap plus map and the value of C is infinity which is greater than 1,so
we change this value to 1 and we’ll say that ‘C’ is coming from (D,C),edge (C,D).At this point
‘D’ is done exploring all its neighbors so we again go to this heap plus map and do
an extractMin here.So this time (C,1) comes out.So first thing we check is
where,who introduced this (C,1) into this heap plus map and that’s we go to this
vertex and that is (C,D).So (C,D) is also in final result and we’re gonna do extract
Min on this heap plus map.Now we’re gonna explore neighbours of ‘C’.So C’s first neighbour
we explore is ‘B’.Now the value stored with ‘B’ right now is 3. Well this edge has a weight 1 which is
less than 3 so this edge is better than what we have in here so we’ll change
this to 1 and we’ll say that B’s edge is (B,C). Then we’re going to explore other
neighbors of ‘C’,so that’s ‘D’.D’s not in this heap plus map data structure so
we’ll ignore ‘D’ and then we’re going to explore ‘F’.’F’ is there in this data structure and
the,and the value attached with ‘F’ is infinity which is the greater than 4 so
we’re going to replace this with 4. And we’re going to say that ‘F’ is coming
from this edge (C,F).They we’re gonna explore this neighbour ‘E’ and the value attached with ‘E’ right
now is 6 which is greater than this edge weight 5, so we’re going to replace this with 5
and then here we are going to say that ‘E’ is coming from (C,E) now.At this
point of time we’re done exploring all the neighbors of ‘C’,so we again go here
and do an extractMin. So this point,at this point we’re
going to extract ‘B’ out of this heap plus map and we’re gonna go and check which
edge introduced ‘B’ and that is (B,C). So (B,C) will go into the final
result and we’re gonna remove ‘B’ from this heap plus map data structure.
Now we’re gonna explore neighbors of ‘B’.So 1st we go to B’s ‘A’. It is not there in the c plus,heap plus
map data structure so we ignore it. It’s another neighbour is ‘D’.’D’ is also
not there so we ignore it,another neighbour is ‘C’ ‘C’ is also not there in this heap plus map.So we
ignore it as well.So now we move to the next,we’re gonna again do a extractMin on
this heap plus map.So next time we did is ‘F’ is 4.So 1st time we do is check
who introduced ‘F’ and that is edge (C,F).So (C,F) is also in final result and
we’ll remove (F,4) from here.So we’ll explore neighbours of ‘F’. So the 1st neighbor of ‘F’ is ‘C’ but ‘C’ is
not in this data structure so we ignore it and the next neighbour of ‘F’ is ‘E’ and the
value attached with ‘E’ here is 5 while this edge gets it done in 2 so replace this
5 with 2. And let’s say that ‘E’ is now coming from
(E,F) and then at this point of time we’re done exploring all the neighbours of ‘F’. So we go back here and we extract this last
guy out and we check who introduced this value 2. So that’s (E,F).So (E,F) is also in
final result. and we remove this guy from here and
we’ll look at its neighbours. So we go to ‘D’.’D’ doesn’t exist in this map,
in this data structure,’E’ doesn’t, ‘C’ doesn’t exist here and ‘F’ doesn’t
exist here.So we have totally done exploring ‘E’ at this point of time. So we go back here,at this point this heap
plus map data structure has no elements, it means that all the vertices have
been covered and we got our minimum spanning tree edges. So the edges
for this minimum spanning tree is this 1, this 1,this 1,this 4 and this 2. So let’s analyze the time and space
complexity.Space complexity is prettty straight forward.This,we are storing result,
we’re storing this map and we are storing heap plus map data structure.In the
worst case the space complexity will be E +V because we might have to store
all the edges of this graph. What about the time complexity? So we are
performing this operation on,so we’re performing so as
many edges we have we’re performing that operation that
many times on this heap plus map data structure.In the worst case the size of
this heap plus map data structure will be O(V), basically the size of the entire heap,
entire graph and we’re doing,in worst case ‘E’ operations on this thing and we
know that ‘contains’ work in O(1) time,extractMin works in O(logn)
time,add works in O(logn) time and decrease key works in O(logn)
time.So in worst case the time complexity will be O(Elog(V))
where ‘V’ is the size of this heap plus map data structure.So again the space
complexity is O(V+E) and then the time complexity will be O(Elog(V)).
So in the next section let’s look at that code for this algorithm.So the name of the
function is primMST.It takes in a graph and returns a list of edges which
form the minimum spanning tree. Let’s first initialize the data structure
which we’re going to use. So the first one is the binary min heap
which is the heap plus map data structure I discussed before. So if you want you can look at the class
to see how I’ve implemented it.Then the next data structure is a map from vertex
to edge,basically storing the edge which entered,which provided the
minimum value for this vertex in this min heap.And then finally this is a list
of edges which is just going to store the final result. So first thing we do is we iterate
through all the vertices in this graph and add them to the min heap with
the value, Integer.MAX_VALUE which is basically an infinity value and then
we randomly select start vertex from this graph and then decrease the weight
of that vertex in this min heap to 0. So basically this,this is the 1st
vertex which will get selected and then we go into this while loop until this
min heap has,is not empty. Then we select a vertex so then our
current will be the 1st,will be the minimum value vertex
in this min heap and then we check if this current has a
corresponding edge in this vertex to edge graph, map or not. So this will be missing for the start
vertex but it, this value should be available for every
other,other vertex so we check if the spanning tree edge is not null. If it is
not then we add it to the final result and then we are going to get every edge
for this,for this current vertex and then get the adjacent vertex for this
edge and then we’re going to check if this adjacent,adjacent vertex
exist in the min heap or not and if it does exist then is the weight attached
with this vertex greater than the edge weight or not.If both the
conditions are true basically if it exists in the min heap and the weight
attached,the current weight attached with this adjacent vertex is greater
than the edge weight then we’re going to go into the min heap and decrease the
value of that vertex to the current edge weight and then we’re going to add
this vertex and the edge into this vertex to
edge map and then we’re going to repeat the process for other edges of this
current vertex and once we are done totally exploring this vertex we’re going to go back and go to the top
and repeat the same process,basically again doing an extractMin for,
and getting another current vertex and then going through its neighbors and updating
the min heap. And finally the result will be stored
final result will be stored in this result list and we’ll just return this
list. So again the time complexity is O(E+V),
and space, time complexity is O(ElogV) and space
complexity is O(E+V).So this is all I’ve to talk
about Prim’s algorithm.Please like this video,share this video,comment on this
video,check out my facebook page facebook,facebook.com/tusharroy25
and check out my github link github.com/mission-peace/interview/wiki. Thanks again for watching this video.

100 thoughts to “Prim’s Algorithm Minimum Spanning Tree Graph Algorithm”

  1. Saving me in exam time… For placement preps it is very useful… do more videos as much you can… lol

  2. I now type algo name Tushar Roy in Youtube search bar for my exams! ๐Ÿ™‚ But plz see my doubts in your DP videos.

  3. why unlike others,you didn't check edges already in set and upcoming edges makes cycle with it or not . is it different algo?

  4. for those who came for details for min binaryheap from tushar's dijkstra algorithm video, watch from 1:15 to 5:55. cheers !

  5. if we are implementing this in c++ then i think it would be better to use STL set instead of STL priority queue since when we gonna be updating the edge in the priority queue first we need to erase it and then insert it again and since priority queue doesn't have erase method but set has , it would be better to use set.
    i am a novice, please correct me if i am wrong.

  6. Sir, You are an excellent teacher and a wonderful person to help a lot of needy ones like me here. Thank u so much. Please keep up the good work!

  7. Why would it use O(V + E) auxiliary space? Heap would have maximum V vertices and map would store only 1 edge per vertex(the edge with minimum path to that vertex).

  8. You can really teach. Thank you for all your hard work. You're the exact opposite of all those professors clogging up the halls and offices at uni, because you can actually make this stuff easy to understand for human beings.

  9. Your explanations of these graphing algorithms by far the the most thorough and clear. thank you so much for doing these.

  10. Thanks a ton!! All your videos are extremely helpful ,especially before exams! Upload more videos as much as possible, you make things look so simple and easy.

  11. Tushar.. Do we really need resultList as the vertexToEdge map itself holds all the edges required for the result? Can the vertexToEdge map acts as the result set?

  12. Excellent explanation! Keep it up. If 2 edges are found with same weight , which edge should I choose? After Step1, Can I choose edge BD instead of edge AB?

  13. mate because of you i could do one problem at university, thank you and good luck :-* (sorry for the bad english, not my native language)

  14. At 2:07,I see why contains() is O(1).
    But why is findMin() O(logN).Shouldnt it be O(1) since you can directly access the heap root in O(1).
    Correct me if I am wrong.

  15. The source code on GitHub called primMST is missing a couple of class source code files such as Edge, Graph, and Vertex. Where are they?

  16. shouldn't the decrease function work so that decrease(f,2) would subtract 2 from (f,7) and reposition it's location in the tree? so instead of repositioning (f,-2) as is in the video, it should reposition (f,5)?

  17. I think your code will go into an infinite loop if the graph is disconnected. Nice explanation anyways, thanks.

  18. Hi Tushar,Really loved the way you explained!!!In binary heap of ur code,i have a doubt,wen you update NodePosition map,y dont u update allNodes position.Because in few areas of your code you take node depending on postion from map.

  19. Thankyou for the video!!
    Can you please upload the link of how to construct heap + map datastructure in c++ . I am not able to find it.

  20. I may be mistaken, but I think the operation while he's visiting C and replaces the AB edge of cost 3 with the BC edge of cost 1 is incorrect.

    Again, I may be mistaken here, but I was under the impression you have to compare the cost of the edge (BC: 1) with the total cost to get to the edge from A (AD: 1 + CD: 1 = 2), or 2+1 = 3, and since 3 is not less than the current value stored, B's path to edge (AB: 3) is not overwritten.

    I think what was done here in this specific case (just the CB edge, not the rest), was similar to how edges are selected for Kruscal's algorithm.

    BC is still a valid edge of one of the MSTs of this particular graph, but what I'm saying is the reasoning of WHY the decision to replace AB with BC was incorrect under Prim's algorithm.

    In other words, with his reasoning, if the edge BC was weighted 2, he would have still selected BC as the new edge to get to B from A, which would have resulted in a non-minimum spanning tree (ADCB: 1+1+2 = 4 vs AB: 3).

  21. what would be the cost of traversal for 9 or 10 as once a person has reached B node it need to return to C so that it could traverse further

  22. Can you check if the formulae you had for children and parents were right? Coz. in Binay Heap this is how I implement it.

    – Left child: 2 * i
    – Right child: 2 * i + 1
    – Parent: i / 2

  23. Hello friends , By being a student of computer science student there are lots of videos related to particular topic. so to find which one is useful among them is difficult to find . so due to my channel i hope it will be easy for you to find the useful video by 1 click only. easy for you : https://www.youtube.com/channel/UCGXlUGE29uFvpsNUO7-gikQ To Subscribe :https://www.youtube.com/channel/UCGXlUGE29uFvpsNUO7-gikQ?sub_confirmation=1

  24. Very well done – I appreciate your pacing throughout the lesson. You start the video building the foundation we need to then understand later parts of the lesson – that is key!

  25. Hi,
    I have one question
    Instead of storing the edges in the result set can't we just print the values of hashmap at the end to print the result ,since the values will be overridden whenever there is an update of weight?

  26. Shouldn't the order be ['AD', 'DC', 'CB', 'CF', 'FE'] where CD->DC ,BC->CB, EF->FE. he started with ( smallest element in dictioary+visited vertices) but later he changed the order. Correct me if i'm missing anything here

  27. Why does extract min takes O(logn) time ? We only need the first element of the heap, so shouldn't it be O(1) ?

  28. how is contain operation take O(1) time? dont we have to traverse the whole map, hence it should take O(n) time?

  29. you where talking a little faster than in your other videos, for me it was a little too fast, pls slow it down a bit next time

  30. Sir how can we impliment decrease key operation in priority queues in java …….as heaps can also be created using priorityqueue in java

  31. In Binary Heap implementation, for node class he has used weight. Can anyone tell me what is the purpose of using weight attribute for node class ?

  32. Nice, I am confused why my other logic using Dijkstra's is not working and this is best explanation as least its showing right result. https://stackoverflow.com/a/25800210/1391499 I tried but not getting result and other in a book its written to use new d = weigh[x][v] + dist[v] {adj of x} and pass the new d with the priority queue and just add weight[x][v] to the distance array.

Leave a Reply

Your email address will not be published. Required fields are marked *