Hello friends my name is Tushar and today we're going to talk about how to
find minimum spanning tree using Kruskal's Algorithm.
So what is a spanning tree? A spanning tree of an undirected graph is a sub
graph such that all the vertices are connected to each other and then there
is n-1 edges in this subgraph where n is the total number of vertices.
So basically the subgraph represents a tree.
What is the minimum spanning tree of a weighted undirected graph?
A minimum spanning tree is a tree, is a spanning tree such that the sum of
the weight of the edges is minimum.
So if you look at this example here the minimum spanning tree for this graph
will consist of three edges (A,B),(B,C) and (D,C).So we have 4 vertices, we have
3 edges and all the 4 vertices are connected to each other to form a tree.
So for this video I assume that you know what disjoint sets is because it's a
pre-requisite to understand this algorithm.
I have another video discussing disjoint sets using path compression and
if you have not already watched that video please watch that video before
watching this video.
So in the next section let's try to find the minimum spanning tree for this
example here. The idea of this algorithm is very simple.
First thing we do is we sort the edges in non decreasing order,then using this
makeSet operation of disjoint sets we create as many disjoint sets as the number,
total number of vertices. Then we pick one edge at a time in the non
decreasing order and check both the ends of this edge and see if they're in the same
disjoint sets or different. If they are in the same
disjoint set we ignore this edge if they are in different disjoint sets we merge
those disjoints sets into 1 and put this edge into the final result.
So let's try with this example here. So i've already created 6 different
disjoint sets and I have already sorted edges in non decreasing order so first
let's pick this edge
(A,D). So 'A' and 'D' are in 2 different disjoint sets. So we'll pick (A,D) into final result
and using this union operation of disjoint set we'll merge 'A' and 'D'.So this will
become 'A' and 'D'
in 1 set. Then we are going to pick the next
edge (B,C). So 1st we're going to check,'B' and 'C' again are in 2 different disjoint
sets so (B,C) is also going to be in the final result and we're gonna merge 'B' and 'C'
using this union operation of disjoint sets.
Then we're going to pick edge (C,D). So let's say this disjoint is
represented by 'A' and this disjoint set is represented by 'B', so we'll do findSet
and find 'C' and 'C' belongs to set 'B' and we do a findSet and find 'D' and 'D' belongs
to set 'A'. So basically they are in two different disjoint sets so we'll
again pick (C,D) for the final result and do the union of these two sets.So we'll
have one set here
(A,B,C,D) and let's say this set is represented by 'A'
so then we are going to pick (E,F),so
'E' and 'F' are in 2 different disjoint sets.So (E,F) is also in the final result and we're gonna do
union of 'E' and 'F'.
Then we're gonna pick the next edge (B,D).So 'B' is represented by 'A' and 'E' is
represented by 'A' which tells us that 'B' and 'D' are in the same disjoint sets
right now,so we'll just ignore this edge. Then we'll pick the next edge (A,B).'A' is
represented by 'A' and 'B' is also represented by 'A'
which tells us that 'A' and 'B' are in the same disjoint set,so again we'll ignore this
edge here
(A,B). Then we'll pick the next
edge (C,F). So 'C' is,'C' is in the set 'A' and 'F' is
the set 'E' and so they are in two different sets
So we'll again pick this edge (C,F) and merge these 2 disjoint sets. And then we'll pick (C,E)
and 'C' is represented by and 'C' is represented by 'A' and 'E' is represented
by 'A'
which tells us that 'C' and 'E' are in the same set so we'll again ignore this
edge. And lastly (D,E), 'D' is represented by 'A' and 'E' is represented by 'A',basically
telling us that they are also in the same
they're also in the same disjoint set, so we'll again ignore
'D'.So these are the edges which form the minimum spanning tree for this graph here.
(A,D),(B,C),(C,D),(E,F) and (C,F) here.So this 5 edges form together minimum spanning
tree.
So what is a space complexity? Space complexity is,in the worst case whatever
disjoint sets takes and whatever
this result,whatever we're storing the result so it will be O(V+E). What is the time
complexity for this algorithm?
So it will take,so if we have 'E' edges
it will take O(ElogE) time to sort these edges in non decreasing order
and then if you have watched my video on disjoint set
so you would know that if,if there are 'n' operations on disjoint set it takes
O(n) time.
So rest of this operation would in worse case take O(E) time,so O(ElogE+E).
So in the next section
let's look at the code for this algorithm. Code like algorithm is very simple.
So the name of the function is get minimum spanning tree and it passes us a
graph.First thing we do is we get all the edges of this graph and then we sort
the edges in non decreasing order and then we initialize a class of dis-
-joint sets,set and what we do is we create as many disjoint sets as the
total number of vertices using this makeSet operation of disjoint set.
And then we are going to do is iterate through each of the edges in non
decreasing order and for every edge, get the 2 vertices of this edge and see
if they are in same disjoint set or different disjoint set.So we get the
root, we get the name of the set for all, for these 2 vertices of the
edge using findSet operation and check if they are in the same set.If
they're in the same set it means we're going to ignore this edge and if they're
in the different set then we're going to add this edge into the final result and
also do the union of these 2 sets into 1 and then we move on to the next edge
and we keep doing this until we have edges to iterate through. And then finally
return
all the edges in the result edge.So as I said again the runtime complexity
is O(ElogE) to sort this,the edges and then O(E) to do these
operations and the space complexity is O(E+V).
Thanks again for watching this video. Please like this video,share this video
comment on this video,check out my facebook page at facebook.com/
tusharroy25 and check out my github link github.com/mission-peace/
interview/wiki.
Thanks again for watching this video.