FREE E LEARNING PLATFORM
☰ HOMEEXCEPTIONSOOPSJVMINTRO
SYLLABUS TUTORIALS FORUM
 

Kruskal's Algorithm



Introduction

Kruskal's Algorithm is a Greedy Algorithm used to construct the Minimum Spanning Tree (MST) of a connected weighted undirected graph. Instead of starting from a particular vertex, the algorithm begins by selecting the edge with the smallest weight. It repeatedly adds the smallest edge that does not form a cycle until all vertices become connected.

The algorithm always chooses the minimum-weight edge available and avoids cycles using the Union-Find (Disjoint Set) data structure. The final tree connects all vertices with the minimum possible total edge weight.

Why Do We Need Kruskal's Algorithm?

Many engineering problems require connecting multiple locations at the minimum possible cost. Kruskal's Algorithm provides an efficient solution by selecting the cheapest edges first while ensuring that no cycles are formed.

Application Purpose
Computer Networks Connecting computers with minimum wiring cost.
Road Networks Connecting cities using minimum construction cost.
Electric Power Systems Designing economical transmission networks.
Water Distribution Installing minimum-cost pipeline systems.
Telecommunication Connecting communication towers efficiently.

Prerequisites

Concept Description
Graph A collection of vertices connected by edges.
Weighted Graph Each edge has an associated weight.
Minimum Spanning Tree A spanning tree having the minimum total edge weight.
Disjoint Set (Union-Find) Used to detect cycles efficiently.

Working Principle

Kruskal's Algorithm sorts all edges in ascending order of their weights. It then selects the smallest edge one by one. An edge is added to the Minimum Spanning Tree only if it does not create a cycle. This process continues until exactly (V − 1) edges are selected.

Illustration


Edges After Sorting

D ---- E (1)

A ---- C (2)

C ---- E (3)

A ---- B (4)

B ---- C (5)

B ---- D (6)

Selected Edges

D ---- E

A ---- C

C ---- E

A ---- B

Total Cost = 10

Figure 1 : Construction of MST using Kruskal's Algorithm

Step-by-Step Example

Step Selected Edge Total Cost
1 D → E (1) 1
2 A → C (2) 3
3 C → E (3) 6
4 A → B (4) 10

Kruskal's Algorithm

Kruskal(Graph) Step 1 : Arrange all edges in ascending order of their weights. Step 2 : Select the edge having the minimum weight. Step 3 : Check whether adding the edge forms a cycle. Step 4 : If no cycle is formed, include the edge in the MST. Step 5 : Otherwise, discard the edge. Step 6 : Repeat until (V − 1) edges are selected.

Complexity Analysis

Operation Time Complexity Remarks
Sorting the Edges O(E log E) Edges are sorted before processing.
Union-Find Operations O(E α(V)) Cycle detection using Disjoint Set.
Total Time Complexity O(E log E) Sorting dominates the execution time.
Space Complexity O(V) Required for the Disjoint Set data structure.

Advantages of Kruskal's Algorithm

  • Produces the Minimum Spanning Tree efficiently.
  • Simple to understand and implement.
  • Suitable for sparse graphs.
  • Avoids cycles using the Disjoint Set (Union-Find) technique.
  • Guarantees the minimum total edge weight.

Limitations of Kruskal's Algorithm

  • Applicable only to connected weighted graphs.
  • Sorting all edges increases execution time for very large graphs.
  • Requires the Union-Find data structure.
  • Cannot directly generate an MST for disconnected graphs.

Applications of Kruskal's Algorithm

Application Description
Computer Networks Designing low-cost communication networks.
Road Construction Connecting cities with minimum construction cost.
Power Distribution Designing economical electrical transmission systems.
Water Pipeline Networks Installing pipelines using minimum total cost.
Cable TV Networks Reducing cable installation expenses.

Comparison of Prim's Algorithm and Kruskal's Algorithm

Prim's Algorithm Kruskal's Algorithm
Starts from any vertex. Starts from the minimum weighted edge.
Builds one tree throughout execution. Builds several small trees and merges them.
Uses a Priority Queue. Uses Union-Find (Disjoint Set).
Better suited for dense graphs. Better suited for sparse graphs.
Time Complexity : O(E log V) Time Complexity : O(E log E)

Important Points

  • Kruskal's Algorithm is a Greedy Algorithm.
  • Edges are selected in ascending order of weight.
  • The algorithm never allows a cycle.
  • The final Minimum Spanning Tree contains exactly (V − 1) edges.
  • The Union-Find (Disjoint Set) data structure is commonly used for cycle detection.

Exam Tip

AKTU examinations frequently ask students to construct a Minimum Spanning Tree using Kruskal's Algorithm. Remember the three important steps: Sort the edges, Select the smallest edge, and Avoid cycles. Also remember the comparison between Prim's Algorithm and Kruskal's Algorithm.

Summary

Kruskal's Algorithm is one of the most widely used Greedy Algorithms for constructing a Minimum Spanning Tree. It repeatedly selects the smallest weighted edge while ensuring that no cycle is formed. Due to its efficiency and simplicity, it is widely used in communication networks, transportation systems, electrical power distribution and many other optimization problems.







Copyright 2020 by Noidatut. All Rights Reserved.

Noidatut.com