AI WisdomApply this in AI systems ↗

PyAnimate

Interactive Python Lab

AI Wisdom

Loading playground…

PyAnimate

Interactive Python Lab

AI Wisdom

Interactive Python Lab

Kruskal's MST

The playground auto-runs on load. Hit Run My Code to trace your own Python — every step animated live.

Explain·Line by line

Replay·Step by step

Challenge·Guided prompts

XP·...

Data Flow Pipeline

mastery Track

Dijkstra's Shortest Path

0/1 Knapsack DP

Longest Common Subsequence

Coin Change DP

Topological Sort (Kahn's)

Kruskal's MST

Trie (Prefix Tree)

Floyd-Warshall All-Pairs Shortest Path

Segment Tree for Range Queries

Bit Manipulation Tricks

Explain

Line 2

Initialize Union-Find

Why this approach?

Each vertex starts as its own parent — every node is its own component initially. parent[i] = i means 'i is a root.'

Structured Explanation

Overview

Kruskal's algorithm finds the Minimum Spanning Tree by greedily adding the cheapest edge that doesn't form a cycle.

Analogy

Laying power cables between cities: always connect the next cheapest pair that isn't already indirectly connected.

Step-by-step

Sort all edges by weight ascending.
For each edge (u,v,w): if find(u) != find(v): add edge and union(u,v).
Stop when V-1 edges added (spanning tree complete).
Use Union-Find with path compression and rank for efficiency.

Visual

Edges sorted: (1,2,1),(1,3,2),(2,4,2),(3,4,3) → MST uses first 3 edges with total weight 5.

Common mistakes

Not sorting edges first.
Missing Union-Find → cycle check is O(V) per edge instead of O(α(V)).

Practice questions

Implement Kruskal's with Union-Find; output MST weight.
Compare Kruskal vs Prim for dense vs sparse graphs.

Time

O(E log E)

Space

O(V+E)

Complexity

Time

O(E log E)

Space

O(V)

Complexity Overview

O(1)

O(log n)

O(n)

O(n log n)

O(n²)

n = 8range 1-20

AT N = 8

Complexity	Operations
O(1)	1
O(log n)	3
O(n)	8
O(n log n)	24
O(n²)	64

Challenge

Find MST of edges: (A-B,4), (A-C,2), (B-C,1), (B-D,5), (C-D,8). Show sorted edges and union-find steps.

Hint

Sort edges by weight. Use Union-Find to detect cycles. Greedily add edges that don't form a cycle.

Code Studio

Kruskal's MST

Monaco Ready

Python ready

lesson.pyline 2

Loading editor...

Output Console

3 lines

❯ [(1, 2, 1)]

❯ [(1, 2, 1), (1, 3, 2)]

❯ [(1, 2, 1), (1, 3, 2), (0, 2, 3)]

Real-World Applications

Network design

Circuit design

Clustering

Road planning

Loading playground…

Interactive Python Lab

Kruskal's MST

The playground auto-runs on load. Hit Run My Code to trace your own Python — every step animated live.

Explain·Line by line

Replay·Step by step

Challenge·Guided prompts

XP·...

Data Flow Pipeline

mastery Track

Dijkstra's Shortest Path

0/1 Knapsack DP

Longest Common Subsequence

Coin Change DP

Topological Sort (Kahn's)

Kruskal's MST

Trie (Prefix Tree)

Floyd-Warshall All-Pairs Shortest Path

Segment Tree for Range Queries

Bit Manipulation Tricks

Explain

Line 2

Initialize Union-Find

Why this approach?

Each vertex starts as its own parent — every node is its own component initially. parent[i] = i means 'i is a root.'

Structured Explanation

Overview

Kruskal's algorithm finds the Minimum Spanning Tree by greedily adding the cheapest edge that doesn't form a cycle.

Analogy

Laying power cables between cities: always connect the next cheapest pair that isn't already indirectly connected.

Step-by-step

Sort all edges by weight ascending.
For each edge (u,v,w): if find(u) != find(v): add edge and union(u,v).
Stop when V-1 edges added (spanning tree complete).
Use Union-Find with path compression and rank for efficiency.

Visual

Edges sorted: (1,2,1),(1,3,2),(2,4,2),(3,4,3) → MST uses first 3 edges with total weight 5.

Common mistakes

Not sorting edges first.
Missing Union-Find → cycle check is O(V) per edge instead of O(α(V)).

Practice questions

Implement Kruskal's with Union-Find; output MST weight.
Compare Kruskal vs Prim for dense vs sparse graphs.

Time

O(E log E)

Space

O(V+E)

Complexity

Time

O(E log E)

Space

O(V)

Complexity Overview

O(1)

O(log n)

O(n)

O(n log n)

O(n²)

n = 8range 1-20

AT N = 8

Complexity	Operations
O(1)	1
O(log n)	3
O(n)	8
O(n log n)	24
O(n²)	64

Challenge

Find MST of edges: (A-B,4), (A-C,2), (B-C,1), (B-D,5), (C-D,8). Show sorted edges and union-find steps.

Hint

Sort edges by weight. Use Union-Find to detect cycles. Greedily add edges that don't form a cycle.

Code Studio

Kruskal's MST

Monaco Ready

Python ready

lesson.pyline 2

Loading editor...

Output Console

3 lines

❯ [(1, 2, 1)]

❯ [(1, 2, 1), (1, 3, 2)]

❯ [(1, 2, 1), (1, 3, 2), (0, 2, 3)]

Real-World Applications

Network design

Circuit design

Clustering

Road planning