Kruskal’s Algorithm-
- Like Prim’s Algorithm, Kruskal’s Algorithm is another greedy algorithm used for finding the Minimum Spanning Tree (MST) of a given graph.
- The graph must be weighted, connected and undirected.
Steps for implementing Kruskal’s Algorithm-
Step-01:
- Sort all the edges from low weight to high weight.
Step-02:
- Take the edge with the lowest weight and use it to connect the vertices of graph.
- If adding an edge creates a cycle, then reject that edge and go for the next least weight edge.
Step-03:
- Keep adding edges until all the vertices are connected and a Minimum Spanning Tree (MST) is obtained.
Thumb Rule to RememberSimply draw all the vertices on the paper and connect them using edges with minimum weights such that no cycle gets formed. |
Time Complexity-
Worst case time complexity of Kruskal’s Algorithm = O(ElogV) or O(ElogE).
Explanation-
- The edges are maintained as min heap.
- The next edge can be obtained in O(logE) time if graph has E edges.
- Reconstruction of heap takes O(E) time.
- So, Kruskal’s Algorithm takes O(ElogE) time.
- The value of E can be at most O(V^{2}). So, O(logV) and O(logE) are same.
Special Case-
- If the edges are already sorted, then there is no need to construct min heap.
- So, deletion from min heap time is saved.
- In this case, time complexity of Kruskal’s Algorithm = O(E + V)
PRACTICE PROBLEMS BASED ON PRIM’S ALGORITHM-
Problem-01:
Construct the minimum spanning tree (MST) for the given graph using Kruskal’s Algorithm-
Solution-
For a video solution explaining the solution step by step, watch this video.
Step-01:
Step-02:
Step-03:
Step-04:
Step-05:
Step-06:
Step-07:
Since all the vertices have been included in the MST, so we stop.
Weight of the MST
= Sum of all edge weights
= 10 + 25 + 22 + 12 + 16 + 14
= 99 units
To gain better understanding of the concepts of Kruskal’s Algorithm and to solve more problems,
To practice previous years GATE problems based on Kruskal’s Algorithm,
Download the handwritten notes of “Kruskal’s Algorithm” here-
Get more notes and other study material of Design and Analysis of Algorithms (DAA).
Watch video lectures by visiting our YouTube channel LearnVidFun.