🛣️ Kruskal's Algorithm - Minimum Spanning Tree

Optimize Joe's transportation network by finding the MST

👩‍💻 Joe's Transportation Challenge

🎯 The Mission:

Help Joe find the Minimum Spanning Tree (MST) of a transportation network to minimize the total cost of connecting all cities using Kruskal's algorithm.

📋 Requirements:

  • Find edges forming the MST
  • Input is an N×N cost matrix (1-indexed cities)
  • 0 means no connection, 9999 means unknown cost
  • Output edges as "CityA -> CityB"

Input/Output Specifications

  • Input: N (number of cities), followed by N×N cost matrix
  • Output: Edges of MST as "CityA -> CityB" (1-indexed)
  • Constraints: 2 ≤ N ≤ 20, -50 ≤ cost[i][j] ≤ 50 (except 0 or 9999), cost[i][i] = 0

Example 1: N=3

Cost Matrix:

0 10 20
10 0 15
20 15 0

Output:

1 -> 2
2 -> 3

Example 2: N=4

Cost Matrix:

0 10 20 30
10 0 15 25
20 15 0 35
30 25 35 0

Output:

1 -> 2
2 -> 3
2 -> 4

⚡ Kruskal's Algorithm Explained

How Kruskal's Algorithm Works

  1. Collect Edges: Gather all edges (u, v, weight) from the cost matrix, excluding 0 or 9999
  2. Sort Edges: Sort edges by weight in non-decreasing order
  3. Initialize Union-Find: Use Union-Find to track connected components
  4. Process Edges: Add edge to MST if it connects different components (no cycle)
  5. Output: List edges in MST as "u -> v" (1-indexed)

Example Edge Table (N=3, costs=[[0,10,20],[10,0,15],[20,15,0]])

EdgeWeightAction
1 -> 210Added to MST
2 -> 315Added to MST
1 -> 320Skipped (forms cycle)

Output: 1 -> 2\n2 -> 3

Time Complexity

O(E log E)

Sorting edges dominates, where E is number of edges

Space Complexity

O(N + E)

For Union-Find and edge storage

Why Kruskal's Algorithm?

  • ✅ Guarantees minimum total edge weight
  • ✅ Handles sparse and dense graphs
  • ✅ Efficient with Union-Find
  • ❌ Requires sorting edges

🔍 Step-by-Step Kruskal's Algorithm Demo

Click "Start Demo" to begin step-by-step visualization

Algorithm Progress:

1. Display input and collect edges
2. Sort edges by weight
3. Process edges with Union-Find
4. Display MST edges

Graph Visualization:

Edge Table:

EdgeWeightAction

🎮 Practice Kruskal's Algorithm

Enter inputs, then click "Compute MST"

Test Cases

Example 1: N=3, cost=[[0,10,20],[10,0,15],[20,15,0]] → 1 -> 2\n2 -> 3

Example 2: N=4, cost=[[0,10,20,30],[10,0,15,25],[20,15,0,35],[30,25,35,0]] → 1 -> 2\n2 -> 3\n2 -> 4

📊 Algorithm Analysis

Kruskal's Algorithm Process

  1. Collect Edges: Extract valid edges from cost matrix
  2. Sort Edges: Sort by weight in non-decreasing order
  3. Union-Find: Initialize parent and rank arrays
  4. Process Edges: Add edge if it doesn't form a cycle
  5. Output: List MST edges as "u -> v"

Time Complexity

O(E log E)

Sorting edges dominates, where E is number of edges

Space Complexity

O(N + E)

For Union-Find and edge storage

Key Points

  • Greedy Approach: Selects minimum-weight edges
  • Union-Find: Prevents cycles efficiently
  • Applications: Network design, clustering
  • Limitation: Assumes undirected graph