Lesson 2 � Beginner

BFS & DFS: Traversal Patterns

Graph ko traverse karne ke 2 fundamental tarike hain � BFS (Breadth-First Search) aur DFS (Depth-First Search). Dono ka approach alag hai aur dono ke apne use cases hain.

BFS � Breadth-First Search

BFS graph ko level by level traverse karta hai. Pehle starting node ke sab neighbors, phir unke neighbors, aur so on.

Imagine karo tum ek building mein ho aur pehle poora floor cover karna hai, phir next floor. Yahi BFS hai.

Level 0: A
Level 1: B C
Level 2: D E

BFS order: A ✓ B ✓ C ✓ D ✓ E

Implementation: BFS mein queue use hota hai. Pehle node ko queue mein daalo, phir queue se nikalo, uske sab unvisited neighbors ko queue mein daalo.

from collections import deque

def bfs(graph, start):
 visited = set()
 queue = deque([start])
 visited.add(start)
 
 while queue:
 node = queue.popleft()
 print(node, end=' ')
 
 for neighbor in graph[node]:
 if neighbor not in visited:
 visited.add(neighbor)
 queue.append(neighbor)

DFS � Depth-First Search

DFS graph ko depth mein jaake traverse karta hai. Ek path ko poora explore karta hai, jab tak dead end na aa jaye, phir backtrack karta hai.

Jaise tum ek maze mein ho � seedha andar jaate jaao, jab rasta na mile toh wapas aao aur naya rasta try karo.

DFS path: A ✓ B ✓ D ? (backtrack) ✓ C ✓ E

DFS ek branch poora explore karta hai
phir next branch par jaata hai

Implementation: DFS mein stack ya recursion use hota hai.

def dfs_recursive(graph, node, visited=None):
 if visited is None:
 visited = set()
 visited.add(node)
 print(node, end=' ')
 
 for neighbor in graph[node]:
 if neighbor not in visited:
 dfs_recursive(graph, neighbor, visited)

def dfs_iterative(graph, start):
 visited = set()
 stack = [start]
 
 while stack:
 node = stack.pop()
 if node not in visited:
 visited.add(node)
 print(node, end=' ')
 for neighbor in graph[node]:
 if neighbor not in visited:
 stack.append(neighbor)

BFS vs DFS � Kab kya use karein?

• Shortest path (unweighted graph): BFS use karo. BFS pehle shortest distance par nodes visit karta hai.
• Connected components: DFS aasan hai implement karna. Ek node se start karo aur sab connected nodes mark karo.
• Memory: BFS ko zyada memory chahiye (queue mein sab level ke nodes). DFS kam memory leta hai (sirf current path store karta hai).
• Level-order processing: BFS. Jaise binary trees mein level order traversal.
• Path finding in maze: DFS (backtracking easily hota hai).
• Cycle detection: Dono use ho sakte hain.

Time & Space Complexity

• Time: Dono ka O(V + E) hai � V = vertices, E = edges. Har node aur har edge ek baar visit hota hai.
• Space: BFS ka O(V) worst case (queue mein sab nodes aa sakte hain). DFS ka O(V) bhi hai (recursion stack / visited set).

Try it: code khud likho

graph = {
 'A': ['B', 'C'],
 'B': ['A', 'D'],
 'C': ['A', 'D'],
 'D': ['B', 'C']
}

Common mistakes

• BFS mein queue.popleft() bhool jaana aur pop() use karna � LIFO ho jayega, BFS nahi rahega.
• Visited set mein add karna bhool jaana � infinite loop mein phas jaoge.
• DFS recursion mein base case nahi rakhna � stack overflow ho sakta hai.
• Directed graph mein neighbors ka order galat traverse karna � output alag aayega (par valid hai).