Overview
Kruskal's algorithm greedily ascending weight order mein edges add karke Minimum Spanning Tree (MST) banata hai.
Analogy
Jaise sabse saste cables se saare cities connect karna—sabse saste se start karo, cycles avoid karo.
Step-by-step
- Saari edges weight ke ascending order mein sort karo
- Minimum weight edge lo
- Agar cycle nahi banata (Union-Find) toh MST mein add karo
- V-1 edges hone tak repeat karo
Visual
Edges: (1,2,1)(1,3,3)(2,3,2)(3,4,4)
Sorted: 1,2,3,4
Add: (1,2,1)→(2,3,2)→(3,4,4)
MST weight=7
Common mistakes
- Union-Find ke bina cycle detect karna
- V-1 edges par rukna bhool jana
Practice questions
- Path compression aur union by rank wala Union-Find implement karo
- Kruskal's aur Prim's MST compare karo