Chapter 31: DSA Graphs Traversal
DSA Graphs Traversal – Let’s understand this topic properly and in depth, like I’m sitting next to you with a whiteboard, drawing graphs step by step, explaining every single detail slowly, showing multiple examples, comparing the two main methods side by side, and most importantly telling you when to use which traversal and why they are so important in interviews and real-world applications.
What is Graph Traversal?
Graph traversal means visiting every vertex (node) in a graph exactly once (or sometimes with a specific purpose) in some order.
Unlike trees (which have a clear root and no cycles), graphs can be:
- cyclic or acyclic
- connected or disconnected
- directed or undirected
So we need systematic ways to explore them.
There are two fundamental traversal algorithms for graphs:
- Depth-First Search (DFS)
- Breadth-First Search (BFS)
These two cover almost all traversal needs in competitive programming, interviews, and real projects.
1. Depth-First Search (DFS)
DFS goes as deep as possible along each branch before backtracking.
It’s like exploring a maze: you keep going down one path until you hit a dead end, then backtrack and try the next path.
Core idea: “Explore the deepest possible node first”
How DFS works (step by step)
We usually use recursion (implicit stack) or an explicit stack.
Algorithm (recursive version):
|
0 1 2 3 4 5 6 7 8 9 10 11 12 |
DFS(node): mark node as visited process node (print, store, etc.) for each neighbor in adjacency list of node: if neighbor is not visited: DFS(neighbor) |
Example Graph (we’ll use this for both DFS & BFS)
Vertices: 0, 1, 2, 3, 4, 5
Edges (undirected):
0–1, 0–2, 1–3, 2–4, 2–5, 3–5
Adjacency list:
|
0 1 2 3 4 5 6 7 8 9 10 11 |
0: [1, 2] 1: [0, 3] 2: [0, 4, 5] 3: [1, 5] 4: [2] 5: [2, 3] |
DFS starting from node 0 (possible order):
0 → 1 → 3 → 5 → 2 → 4
Or another valid order:
0 → 2 → 4 → 5 → 3 → 1
Notice: The order can change depending on which neighbor you visit first. But DFS always goes deep first.
DFS Code (most common interview styles)
Recursive DFS (cleanest)
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
def dfs(graph, node, visited): if node not in visited: print(node, end=" → ") visited.add(node) for neighbor in graph[node]: dfs(graph, neighbor, visited) # Usage graph = { 0: [1, 2], 1: [0, 3], 2: [0, 4, 5], 3: [1, 5], 4: [2], 5: [2, 3] } visited = set() dfs(graph, 0, visited) # Possible output: 0 → 1 → 3 → 5 → 2 → 4 → |
Iterative DFS (using stack)
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
def dfs_iterative(graph, start): visited = set() stack = [start] while stack: node = stack.pop() if node not in visited: print(node, end=" → ") visited.add(node) # Push neighbors in reverse order (to match recursion) for neighbor in reversed(graph[node]): if neighbor not in visited: stack.append(neighbor) |
2. Breadth-First Search (BFS)
BFS explores the graph level by level (like ripples in water).
It visits all neighbors of the current node before going deeper.
Core idea: “Explore nearest nodes first”
BFS always uses a queue.
How BFS works (step by step)
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
BFS(start): create queue enqueue start node mark start as visited while queue is not empty: dequeue node process node (print, etc.) for each neighbor of node: if neighbor not visited: enqueue neighbor mark visited |
BFS on the same graph (starting from 0)
Level 0: 0 Level 1: 1, 2 Level 2: 3, 4, 5
Possible order: 0 → 1 → 2 → 3 → 4 → 5
(Exact order depends on which neighbor is enqueued first)
BFS Code (most common interview style)
|
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
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) # Same graph as above bfs(graph, 0) # Possible output: 0 → 1 → 2 → 3 → 4 → 5 → |
DFS vs BFS – Side-by-Side Comparison (very important for interviews)
| Question / Property | DFS | BFS |
|---|---|---|
| Data structure used | Stack (or recursion) | Queue |
| Order of exploration | Deep first (goes deep) | Level by level (wide first) |
| Path finding | Finds any path | Finds shortest path in unweighted graph |
| Memory usage (worst case) | O(V) (skewed graph) | O(V) (wide graph) |
| Cycle detection | Yes | Yes |
| Shortest path (unweighted) | Not guaranteed | Yes (BFS is optimal) |
| Shortest path (weighted) | No | No (need Dijkstra) |
| Typical applications | Topological sort, SCC, maze solving (backtracking) | Shortest path, level order, connected components |
| Implementation complexity | Simpler recursive | Slightly more code (queue) |
Rule of thumb (very common interview answer):
“Use BFS when you need shortest path in an unweighted graph or want to process nodes level by level. Use DFS when you want to explore deep paths, need topological order, or are solving problems with backtracking.”
Most Common Graph Traversal Questions (2025–2026 style)
Easy → Medium:
- Implement DFS & BFS (recursive + iterative)
- Number of connected components
- Check if graph is connected
- Detect cycle in undirected / directed graph
- Find path between two nodes
Medium → Hard:
- Shortest path in unweighted graph (BFS)
- Rotten Oranges / Flood Fill (BFS multi-source)
- Course Schedule / Topological Sort (DFS or Kahn’s BFS)
- Word Ladder (BFS)
- Number of Islands (DFS/BFS on grid)
- Bipartite Graph check (BFS coloring)
Summary – Graph Traversal Cheat Sheet
| Traversal | Explores | Uses | Shortest path (unweighted)? | Best for |
|---|---|---|---|---|
| DFS | Deep first | Stack | No | Topological sort, cycle detection, backtracking |
| BFS | Level by level | Queue | Yes | Shortest path, level order, connected components |
Both run in O(V + E) time (visit every vertex once + look at every edge once)
Would you like to go deeper into any specific traversal topic?
Very natural next steps:
- DFS vs BFS detailed dry run on same graph
- Cycle detection using DFS and BFS
- Shortest path using BFS (unweighted graph)
- Topological Sort using DFS and Kahn’s algorithm (BFS)
- Number of Islands (grid as graph – very common pattern)
- Bipartite Graph check using BFS coloring
Just tell me which one you want next — I’ll explain it in the same detailed, human-teacher style with clear examples, visuals, and code! 😊
