Kruskal’s algorithm for computing minimum
spanning tree of a graph. Now, let’s start off with some basic definitions.
What is a spanning tree? A spanning tree is a subgraph that has the same vertex set as
the original graph and is also a tree which means that it must be connected and must not
contain any cycles. A graph may have large number of spanning trees but not all of them
are minimum. A minimum spanning tree is the one in which the sum of weight of edges is
minimum Now, let’s look at the steps for finding
the minimum spanning tree using Kruskal’s algorithm. The steps are fairly simple. The
first one says sort all the edges in non-decreasing order of their weight. Now, this is a greedy
algorithm. So, what it does is that it picks the smallest weighted edge not in the spanning
tree. Checks if adding this edge to our spanning tree obtained so far forms a cycle or not.
If not, then this edge will be a part of our minimum spanning tree. If it forms a cycle,
we discard it. We need to keep repeating this step for all edges in G until there are exactly
V-1 edges in our minimum spanning tree where V is the number of vertices in G. Now, let’s try and understand these steps
with an example. Consider the given graph which has 9 vertices, v0 to v8. The numbers
on the edges represent the weight of that edge. We need to obtain a minimum spanning
tree of the given graph. The 1st step says sort all edges in non-decreasing order by
their weights. Let’s do that. You can see that all the edges
are written in the sorted order by their weights. v7v6 being the smallest weighted edge with
weight 1 and v3v5 being the maximum weighted edge with weight 14. Now, let’s move on to
step 2. Pick the smallest edge v7v6. Being, the 1st
edge, it obviously does not form any cycle. So, this edge will definitely be a part of
the minimum spanning tree. The edges represented by the yellow lines are the ones that are
part of our MST. Let’s pick the next edge v8v2. Again, it doesn’t
form any cycle, so it will be added to the MST. Next is v6v5. Again, no cycle being formed.
Add it to the MST. Now Pick v0v1, check for cycles. No cycle
formed, add this edge to the MST too! Next is v2v5, again adding this edge to MST
doesn’t form a cycle. This edge will also be a part of the MST Now, let’s look at v8v6. If we add this edge
to MST, it forms this cycle, as you can see here. So, this edge won’t be a part of the
MST. Adding v2v3 to the MST doesn’t lead to the
formation of any cycles. So, v2v3 will also be an edge in the MST. Now, v7v8 can’t be a part of the minimum spanning
tree because adding this edge would form this big cycle, this one. Adding v0,v7 to MST doesn’t form any cycle.
So, it will be added to the minimum spanning tree too. Also, note that we’re keeping a
track of the no. of edges in MST. because according to the 3rd step, we need to stop
as soon as we have V-1 edges, which is 8 in this case. Let’s try and add v1v2, note that a cycle
is being formed, so v1v2 won’t be in the MST. Next is v3v4. Adding v3v4 doesn’t form any
cycle. So, add this edge to the MST. Note that we have now 8 edges in our minimum spanning
tree. So, we have reached the terminating condition. Thus, we have successfully obtained the minimum
spanning tree of the given graph. We can also calculate the weight of this MST by adding
the weight of individual edges in this tree. We see that they add up to 37. Now, let’s have a look at the pseudocode for
this algorithm. Line 1 initializes A to an empty set.
Lines 2 and 3 create V trees, each containing one vertex.
Line 4 simply sorts all edges in the original graph by no decreasing order of their weights.
In lines 5-8, we one by one pick edges in the order of their weight, lowest to highest.
The loop checks for each edge u,v , whether the end points u and v belong to the same
tree. If they do, adding them to the MST would form a cycle. So, it’ll be discarded. But
if not, line 7 adds edge uv to the MST. Line 8 merges the 2 trees using u and v.
Finally, return the set A containing all the edges belonging to the minimum spanning tree. Now, let’s analyse the complexity of Kruskal’s
algorithm for minimum spanning trees. Initializing A to an empty set takes constant
time. The make set operation in lines 2 to 3 grows
very slowly. Sorting E edges takes O(ElogE) time
Lines 5 to 8 perform the find set and union operation for each edge in G. Thus, taking
a time of O(ElogV) So, Overall Complexity of Kruskal’s algorithm
is O (E LogE + E LogV). But value of E can be atmost O(V2), so O(LogV) and O(LogE) are
same in this case. Therefore, overall time complexity is O(ElogE) or O(ElogV). Thank you for watching the video. Please leave
us your comments.