Interactive Python Lab

Kruskal's MST

Playground load hone par auto-run hota hai. Apne Python ko trace karne ke liye Mera Code Chalao par click karein — har step live animated.

Samjhein·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

Samjhein

Line 2

Initialize Union-Find

Yeh approach kyun?

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 algorithm Minimum Spanning Tree (MST) banata hai — sabse saste edges chunkar sab nodes connect karo.

Analogy

Jaise cities ko cheapest cable se connect karo — cheapest first, cycle mat banao.

Step-by-step

Sab edges weight ke hisaab se sort karo
Union-Find structure banao
Har edge ke liye: agar dono endpoints alag components mein hain toh add karo
V-1 edges lene ke baad MST complete

Visual

Edges sorted by weight: 1,2,3,4,5... Add cheapest edge if no cycle Stop when V-1 edges added

Common mistakes

Union-Find ke bina cycle detection O(V) per edge
Disconnected graph: V-1 se kam edges MST mein
Path compression aur union by rank bhool jaana

Practice questions

Kruskal implement karo Union-Find se
Minimum cost to connect all cities solve karo

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

N = 8 pe

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

Challenge

Edges: (A-B,4), (A-C,2), (B-C,1), (B-D,5), (C-D,8) ka MST dhundho.

Hint

Edges ko weight se sort karo. Cycle detect karne ke liye Union-Find use karo.

Code Studio

Kruskal's MST

Monaco Ready

Python ready hai

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

1

Network design

2

Circuit design

3

Clustering

4

Road planning

Comments

Loading comments...