Introduction

Kruskal Algorithm is one of the most important algorithms for finding a Minimum Spanning Tree (MST).

You are given:

  • A weighted undirected graph
  • n vertices
  • Weighted edges

Goal:

Find a spanning tree with minimum total weight.

Example

Input

n = 4

Edges:
0 -- 1 (10)
0 -- 2 (6)
0 -- 3 (5)
1 -- 3 (15)
2 -- 3 (4)

Output

MST Cost = 19

Key Observation

Always pick the smallest weight edge that does not form a cycle.

Union Find helps efficiently detect cycles.

Algorithm

  1. Sort all edges by weight.
  2. Initialize Union Find.
  3. Pick the smallest edge.
  4. If it does not create a cycle, include it.
  5. Otherwise skip it.
  6. Continue until MST contains n-1 edges.

Dry Run

Sorted Edges

(2,3,4)(0,3,5)
(0,2,6)
(0,1,10)
(1,3,15)

Pick (2,3,4)

Cost = 4

Pick (0,3,5)

Cost = 9

Pick (0,2,6)

Creates Cycle
Skip

Pick (0,1,10)

Cost = 19

MST completed.

Answer:

19

Approach : Greedy + Union Find

Kruskal greedily picks the smallest edge available.

Union Find ensures that selected edges do not form cycles.

The resulting spanning tree has minimum possible weight.

Practice

Complexity Analysis

Time Complexity: O(E log E)Explanation:
Sorting all edges dominates the running time. Union Find operations take nearly constant time.

Space Complexity: O(V)
Explanation:
An additional parent array of size V is used for the Union Find structure.

Why This Problem is Important

Kruskal Algorithm is one of the most popular MST algorithms and is heavily used in networking, road construction, and graph optimization problems.

Common Beginner Mistakes

  • Forgetting to sort edges.
  • Adding edges that create cycles.
  • Incorrect Union Find implementation.
  • Confusing MST with shortest path problems.

Interview Tip

Always mention:

Kruskal is a Greedy Algorithm that repeatedly picks the smallest edge that does not create a cycle.

Related Questions

  • Prim's Algorithm
  • Min Cost to Connect Points
  • Graph Valid Tree
  • Redundant Connection
  • Number of Connected Components

Final Takeaway

Kruskal Algorithm is a fundamental Minimum Spanning Tree algorithm that combines Greedy strategy with Union Find to efficiently build an MST with minimum total cost.