KRUSKAL'S ALGORITHM
Introduction
Kruskal's algorithm is used to solve the minimum spanning tree(MST) problem. It looks for a MST of a weighted connected graph as an acyclic subgraph with V-1 number of edges(where V is the number of vertices) for which the the sum of edge weights is the smallest.
Working Procedure
- Let MST_E[] be the set of edges that are to be included in the minimum spanning tree. Let edgeCount be the number of edges that are included in MST.
- Let V and E be the no. of vertices and edges in the given graph.
- First, sort all the edges in the increasing order of their weights.
-
Loop until edgeCount < V - 1.
- Let edge e = E[edgeCount].
- If adding edge e to MST_E[] makes the resultant MST an acyclic, then add it and increment the edgeCount.
- Else ignore this edge and move on to next edge.
Time Complexity: O(E * logV)
That's it from this blog post. If you liked it then do share this blog with your friends or people who wanna get into programming world. Thank You!