3.5.4
Socho jaise still paani mein ek pathar giraao. Ripples bahar ki taraf rings mein failti hain — pehle saare points jo 1 unit door hain, phir saare jo 2 units door hain, aur aise hi aage. BFS ek graph ko exactly inhi rings mein explore karta hai (jise levels kehte hain) ek source node se shuru karke.
YE kyun important hai: kyunki BFS nodes ko distance ke badhte order mein visit karta hai, ek unweighted graph mein pehli baar jab woh kisi node tak pahunche, woh shortest path (sabse kam edges) se pahuncha hota hai.
Breadth-First Search ek graph traversal hai jo kisi node ke saare neighbors ko explore karta hai usse pehle ki neighbors ke agle level par jaaye. Yeh ek FIFO queue use karta hai yeh yaad rakhne ke liye ki aage kaun se nodes visit karne hain, aur ek visited set use karta hai taki dobara processing na ho.
YEH kya produce karta hai: ek level-order visiting sequence, ek BFS tree , aur (unweighted graphs ke liye) source se distances shortest-path wali.YEH kaun se data structures use karta hai: ek queue (the frontier) + ek visited/dist array.
Intuition Queue = FIFO = level orderEk queue nodes ko usi order mein serve karta hai jisme woh aaye the. Agar hum pehle source add karein, phir uske saare neighbors (level 1), toh woh level-1 nodes kisi bhi level-2 node se pehle serve honge — kyunki woh queue mein pehle enter hue the. Toh nodes distance ke order mein sorted pop out hote hain. Yahi BFS ka poora raaz hai.
Agar hum stack (LIFO) use karein uski jagah, hum pehle deep dive karte — woh DFS hai, aur woh shortest paths nahi deta.
Hum chahte hain: har node v s d ( v )
Claim jis par hum build karte hain: agar hum pehle se saare nodes distance k k + 1 k abhi tak visited nahi hai.
Steps ki derivation:
Shuru: d ( s ) = 0 s
Ek node u sabse purana → sabse chhota distance). (Sabse purana kyun? Level order maintain karne ke liye.)
u w unvisited hai: woh pehli baar reach hua hai, toh d ( w ) = d ( u ) + 1 w abhi kyun, push ke time par? Taki woh kabhi do baar queue mein na jaaye.)Repeat karo jab tak queue empty na ho jaaye.
BFS(s):
dist[s] = 0
visited[s] = True
queue = [s]
while queue not empty:
u = queue.popleft() # FIFO → smallest dist first
for w in adj[u]:
if not visited[w]:
visited[w] = True # mark at enqueue time!
dist[w] = dist[u] + 1
parent[w] = u # for path reconstruction
queue.append(w)
Worked example Example 1 — ek chhote graph par shortest pathGraph (undirected): 0-1, 0-2, 1-3, 2-3, 3-4. Source = 0.
step
pop
queue after
dist updates
init
—
[0]
d0=0
1
0
[1,2]
d1=1, d2=1
2
1
[2,3]
d3=2 (via 1)
3
2
[3]
3 already visited → skip
4
3
[4]
d4=3
5
4
[]
done
Result: distances { 0 : 0 , 1 : 1 , 2 : 1 , 3 : 2 , 4 : 3 } d3=2 kyun, 3 nahi? Node 3 ko level-1 node 1 se pehle discover kiya gaya, toh shortest path 0→1→3 (length 2) capture ho gayi, na ki 0→2→3 (bhi 2) ya lambi.
Worked example Example 2 — actual path reconstruct karnaExample 1 se parent use karke: path to 4 ko parents ko backward walk karke build kiya jaata hai.
4 → parent=3 → parent=1 → parent=0. Reverse karo → 0,1,3,4 .
Backward kyun walk karte hain? parent[w] store karta hai kisne w discover kiya, toh root tak chain shortest path hai.
Worked example Example 3 — grid as a graph (classic interview)Ek maze grid; har cell upar/neeche/left/right wali open cells se connect hoti hai. Start cell se BFS har cell tak minimum number of moves deta hai. Grid ek implicit unweighted graph hai — adjacency list ki zaroorat nahi, neighbors on the fly compute hote hain.
BFS yahan kyun? Har move ki cost 1 hai (unweighted) → pehla arrival = shortest.
Common mistake Visited koenqueue ki jagah dequeue par mark karna
Kyun sahi lagta hai: "Maine abhi tak isko process nahi kiya, toh visited nahi hai." Intuitively visited = done.
Kyun galat hai: same node multiple baar push ho sakta hai pehle pop hone se pehle, queue ko blow up kar deta hai (up to O ( E ) Fix: push karte waqt hi visited mark karo .
Common mistake Shortest path ke liye BFS koweighted graph par use karna
Kyun sahi lagta hai: BFS shortest path deta hai, aur shortest path wohi chahiye!
Kyun galat hai: BFS edges count karta hai, weights nahi. Weights ke saath, fewer edges ≠ smaller cost.
Fix: non-negative weights ke liye Dijkstra use karo; BFS sirf unit/unweighted edges ke liye. (Special trick: 0–1 weights → 0-1 BFS with a deque.)
Common mistake Neighbor loop ke andar visited check bhool jaanaKyun sahi lagta hai: "dist update harmless hai." Lekin tum re-enqueue karte ho aur ek sahi chhote distance ko overwrite kar sakte ho, ya cyclic graphs mein forever loop ho sakta hai.
Fix: sirf unvisited neighbors ko enqueue karo.
Recall Feynman: ek 12-saal ke bacche ko samjhaoSocho graph ek metro map hai aur tum ek station par start karte ho. Tum pehle apne home station par "0" likhte ho. Phir tum har station ko visit karte ho jo ek hop door hai aur "1" likhte ho. Phir har naya station jo unse ek hop door hai usse "2" milta hai, aur aise hi. Tum hamesha saare chhote numbers khatam karte ho kisi bhi bade number se pehle — jaise floor 1 par sabko check karna floor 2 par jaane se pehle. Jo number tumne likha woh us station tak sabse kam hops hai. "Queue" bas stations ki ek line hai apni baari ka intezaar karti — pehle line mein aaya, pehle jaata hai.
Mnemonic BFS yaad rakhne ka trick"FIFO Floors First" — ek F IFO queue F loors (levels) ko ek ek karke explore karta hai; F irst time jab tum kisi node tak pahuncho woh shortest way hai. (BFS = B roader F irst, S hallow before deep.)
BFS ko kaun sa data structure drive karta hai aur kyun? Ek FIFO queue — yeh nodes ko arrival order mein serve karta hai, level-by-level (distance-sorted) exploration guarantee karta hai.
BFS unweighted graphs mein shortest paths kyun dhundta hai? Nodes ko non-decreasing distance order mein dequeue kiya jaata hai, toh pehli baar jab koi node reach hota hai woh fewest edges se hota hai.
BFS ki time complexity kya hai aur kyun? O ( V + E ) V E
Node ko visited kab mark karna chahiye? Enqueue (push) ke time par, taki same node queue mein multiple baar add na ho.
Weighted shortest paths ke liye BFS galat kyun hai? BFS edge count minimize karta hai, total weight nahi; weighted (non-negative) graphs ke liye Dijkstra use karo.
Shortest path itself ko reconstruct kaise karte hain? parent[w] store karo jab w discover karo, phir target se source tak parents walk karo aur reverse karo.
BFS ke dauran kisi bhi moment par queue mein kya hota hai? At most do consecutive levels k k + 1 k
Shortest path ke liye DFS vs BFS — kaun sa aur kyun? BFS; DFS stack (LIFO) use karta hai aur deep dive karta hai, toh pehla arrival guaranteed shortest nahi hota.
DFS — depth-first traversal (stack/recursion, cycles, components, topological order ke liye use hota hai)Dijkstra's Algorithm (BFS jo weighted graphs ke liye priority queue se generalize kiya gaya)0-1 BFS (0/1 edge weights ke liye deque trick)Graph Representations — adjacency list vs matrix (O ( V + E ) E Connected Components (har unvisited node se BFS chalao)Bipartite Check (BFS 2-coloring by level parity)Shortest Path Tree (parent pointers yeh tree banate hain)
if replaced by stack LIFO
Shortest path in unweighted graph
parent for path reconstruction
