Overview
Depth-First Search (DFS) backtrack karne se pehle har path mein jitna deep ho sake jata hai.
Analogy
Jaise maze mein chalna—dead end milne se pehle ek direction mein jaate raho, phir last junction par wapis aao.
Step-by-step
- Start node visit karo aur visited mein mark karo
- Har unvisited neighbor par recursively DFS karo
- Saare neighbors visit karne ke baad backtrack karo
- Bina recursion ke explicit stack use karo
Visual
1
/ \
2 3
/ \
4 5
DFS: 1→2→4→5→3
Common mistakes
- Visited track nahi karna cyclic graph mein infinite loop
- Recursion base case bhool jana
Practice questions
- DFS se binary tree path sum validate karo
- DFS se connected components identify karo