Kruskal’s Algorithm | Kruskal’s Algorithm Example

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 Remember

Simply 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(V2). 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,

Watch this video

To practice previous years GATE problems based on Kruskal’s Algorithm,

Watch this video

 

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.

Summary
Kruskal's Algorithm | Kruskal's Algorithm Example
Article Name
Kruskal's Algorithm | Kruskal's Algorithm Example
Description
Like Prim's Algorithm, Kruskal's Algorithm is a greedy algorithm used to find the Minimum Spanning Tree of graph. Time Complexity Analysis of Kruskal's Algorithm. Kruskal Algorithm Example.
Author
Publisher Name
Gate Vidyalay
Publisher Logo
Liked this article? Share it with your friends and classmates now-