Overview
Topological sort: Directed Acyclic Graph (DAG) ke nodes ko order karo — dependencies pehle. Course prerequisites classic example.
Analogy
Jaise exam schedule karo — prerequisite subject pehle padhna padega.
Step-by-step
- In-degree calculate karo (kitne edges aate hain node mein)
- In-degree 0 wale nodes queue mein daalo
- Node process karo, uske neighbors ka in-degree ghataao
- Queue khaali hone tak repeat karo
Visual
A->C, B->C, C->D
In-degrees: A=0,B=0,C=2,D=1
Queue: [A,B] -> process -> C in-degree=0 -> [C] -> D
Common mistakes
- Cycle wale graph mein topological sort nahi hota — detect karo
- Multiple valid orderings possible — unique nahi hai
- DAG assume karna — cycle check karo
Practice questions
- Course schedule II solve karo (topological sort variant)
- Build order find karo — compilation dependencies