Overview
Breadth-First Search (BFS) graph/tree ko level-by-level traverse karta hai, next level se pehle current level ke saare nodes visit karta hai.
Analogy
Jaise paani mein pathhar daalne se ripples—center se concentric circles mein bahar failtی hain.
Step-by-step
- Start node queue mein add karo aur visited mein mark karo
- Queue khaali na ho tab tak loop karo
- Current node dequeue karo
- Unvisited neighbors queue mein add karo aur visited mark karo
Visual
1
/ \
2 3
/ \
4 5
BFS: 1→2→3→4→5
Common mistakes
- Enqueue par visited mark nahi karna duplicate processing hoti hai
- list.pop(0) se dequeuing O(n²) ho jata hai
Practice questions
- BFS se binary tree minimum depth nikalo
- BFS se connected components count karo