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 2x0+1 so that's 1
so this is left child and 2x0+2 so this is right child.For 2's left child
we replace
'i' with 2 so 2x2+1 so that's 5 and 2x2+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.