dsa / dsa-hashing
25 mins
DSA Module 11: Graph BFS & DFS Traversals
Why This Matters: Graphs model network topology, social graphs, routing maps, and dependency graphs.
## Graph BFS & DFS Traversals
Exploring graphs using Adjacency Lists and Queue (BFS) / Stack (DFS).
```python
from collections import deque
def bfs(graph, start_node):
visited = set([start_node])
queue = deque([start_node])
while queue:
node = queue.popleft()
for neighbor in graph[node]:
if neighbor not in visited:
visited.add(neighbor)
queue.append(neighbor)
```
MENTAL MODEL & MEMORY LAYOUT
GRAPH BFS (LEVEL-BY-LEVEL): Start (Node 0) ──► Explores Neighbors (1, 2) ──► Explores Neighbors of 1 and 2
COMMON PITFALLS TO AVOID
- Forgetting visited set `visited = set()`, leading to infinite loops in cyclic graphs.
Queue-based BFS Traversal
# Queue tracks level-by-level node exploration in O(V + E) time.
Breadth-First Search finds shortest path in unweighted graphs.
CONCEPT MASTERY CHECKPOINT
Which traversal algorithm uses a Queue to explore graph nodes level-by-level?
NEXT RECOMMENDED LESSON
DSA Module 12: Greedy Algorithms
Challenge: Return total vertices in adjacency list graph.