Kruskal’s Algorithm
To start with, we need to know some basic definitions.
What is a Spanning Tree?
It is a subgraph of an undirected connected graph
What is Minimum Spanning Tree?
MST is the lowest weight of the spanning tree(sum of weights of all the edges).
So what is Kruskal’s Algorithm — it is used to find the minimum spanning tree.
Now let’s understand the algorithm, and then we will look at a simple example.
There are three steps to follow.
First, given a spanning tree, sort all the edges from low to high weights
Secondly, add the lower edges to the spanning tree, keeping in mind that they don’t form a cycle.
Finally, see that all the edges are covered, which results in the minimum spanning tree.
What are the uses of kruskal’s algorithm?
Ho do you think electrical wires are connected? yes you guessed it right they use kruskal’s algorithm.
If we go into computer Networking LAN networks are also connected using kruskal’s algorithm.
Time Complexity of Kruskal’s Algorithm — O(ElogV) where V is the number of vertices and E is the number of Edges
Best case time complexity of Kruskal’s algorithm is O(Elog E) since E is V-1
Example:-
Lets understand kruskal’s algorithm with an example so it will be easy to understand.
Lets take weighted graph -
lets start with the lowest weighted edge which is EF with weight 2
next lowest weighted edge is DE 3
Similarly next edge would be AB with weight 4
Then AF with weight 6. Look for a cycle if a cycle is forming ignore the edge and then go for the one in the order.
And finally DC with edge 7 which covers all the vertices.
This is the final Minimum Spanning Tree.
Here, the number of edges in the above tree equals the number of vertices minus 1. So, the algorithm stops here.
Cost of the spanning Tree — Sum of all the weights of the edges is called cost of the Spanning Tree.
In this case the cost of the Minimum Spanning Tree is AB+AF+FE+ED+CD = 4+6+2+3+7=22