Kruskal’s Algorithm

Learn Kruskal’s Algorithm, a greedy method to find the Minimum Spanning Tree (MST) of a connected, undirected, weighted graph. Step-by-step explanation, example, time complexity, advantages, and comparison with Prim’s Algorithm.

Kruskal’s Algorithm (Minimum Spanning Tree – MST)

Introduction

Kruskal’s Algorithm is a well-known greedy algorithm used to find the Minimum Spanning Tree (MST) of a connected, undirected, and weighted graph.
This algorithm constructs an MST by selecting edges in ascending order of weight, ensuring that no cycles are formed. As a result, it connects all vertices at the minimum total cost.

Basic Idea

The main principle of Kruskal’s Algorithm is:

1. Sort all edges in ascending order of weight.
2. Add the smallest weight edge to the MST if it does not form a cycle.

By repeating this process, the algorithm constructs a spanning tree with the minimum total cost.

Steps of Kruskal’s Algorithm

1. Sort all edges in ascending order of weight.
2. Initialize the MST as an empty set.
3. Select edges one by one:
   • If adding an edge does not form a cycle, include it in the MST.
   • Otherwise, skip it.
4. Stop when V − 1 edges are added to the MST, where V is the number of vertices.

Algorithm (Pseudo Code)

Kruskal(G):

   Sort all edges in increasing order of weight

   Initialize MST = {}

   For each edge (u, v) in sorted edges:

       If adding (u, v) does not form a cycle:

           Add (u, v) to MST

   Return MST

Note: Cycle detection is implemented using Union-Find or Disjoint Set.

Example

Suppose a graph has the following edges:

Step-by-step process:

1. Sort the edges: B–C(1), A–C(2), B–D(3), A–B(4), C–D(5)
2. Add B–C → MST includes B–C
3. Add A–C → MST includes A–C
4. Add B–D → MST includes B–D
5. MST complete (4 vertices → 3 edges)
   Minimum Cost = 1 + 2 + 3 = 6

Time Complexity

• Sorting edges → O(E log E)
• Union-Find operations → approximately O(E log V)

Total Time Complexity ≈ O(E log E) ≈ O(E log V)

Space Complexity

• Disjoint sets and edge lists are used.
  Space Complexity = O(V + E)

Kruskal vs Prim (Brief Comparison)

Advantages

• Conceptually simple and easy to implement.
• Efficient for sparse graphs.
• Guarantees an MST with minimum total cost.
• Fast due to the greedy approach.

Limitations

• Applicable only to connected graphs.
• Requires an additional data structure for cycle detection.
• Less efficient for dense graphs compared to Prim’s Algorithm.

Conclusion

Kruskal’s Algorithm is an effective method for constructing Minimum Spanning Trees.
It ensures minimum cost by adding edges in ascending order of weight.
For sparse graphs, its performance is superior to Prim’s Algorithm, making it widely used in network design and optimization.

Some More: 

• POP- Introduction to Programming Using ‘C’
• DS – Data structure Using C
• OOP – Object Oriented Programming 
• Java Programming
• DBMS – Database Management System
• RDBMS – Relational Database Management System
• https://defineinfoloop.blogspot.com/?m=1