Graph Traversal (DFS & BFS)

1. Introduction

What is Graph Traversal?

Graph Traversal is the process of visiting (checking and/or updating) each vertex in a graph systematically. The two fundamental search strategies are Depth-First Search (DFS) and Breadth-First Search (BFS).

Why study them?

Most graph problems are variants of traversal. Tracing connectivity, checking cycles, finding connected islands, and pathfinding are built on top of DFS and BFS traversal foundations.

Where is it Used?

Social Network Degree Searches: Checking if user A is a friend-of-a-friend of user B.

Web Crawlers: Discovering and indexing web page URLs by scanning outgoing links.

---

2. Mental Models

DFS: The Labyrinth Explorer

Imagine walking through a dark labyrinth holding a string:

You walk as far down a path as possible until you hit a dead-end.

When blocked, you wind up the string and backtrack until you find a side passage you haven't explored yet.

You mark visited rooms with chalk (visited set) to avoid walking in circles.

BFS: Ripple in a Pond

Imagine throwing a stone into a still pond:

The splash is the starting vertex.

The water ripples outward in concentric circles (levels).

All neighbors of distance 1 are visited first, then neighbors of distance 2, then distance 3.

This radial expansion makes BFS ideal for finding the shortest path in an unweighted graph.

---

3. Core Traversals & Implementations

Both algorithms require a visited container to prevent visiting nodes repeatedly in graphs with cycle paths:

DFS: Uses a Stack (usually the implicit system call stack via recursion).

BFS: Uses a Queue to track nodes that are scheduled for expansion level-by-level.

---

4. Visual Expansion Trace

Comparing DFS vs BFS traversal starting from node 0 on the graph 0 -> 1 -> 3 and 0 -> 2:

DFS Order: 0 -> 1 -> 3 -> 2

DFS dives deep along path 0 -> 1 -> 3 first, backtracks to 0, and then visits 2.

BFS Order: 0 -> 1 -> 2 -> 3

BFS visits all immediate neighbors of 0 (1 and 2) first, then visits the neighbors of 1 (3).

---

5. Real-World Examples

Maze Solvers / Backtracking: Using recursive DFS to attempt paths, backing out if blocked.

P2P Torrent Broadcasting: BFS distribution of files to neighbors of distance 1, who forward to distance 2, etc.

---

6. Interview Perspective

How Interviewers Ask This Topic

Interviewers test traversal choice selection:

"Find the shortest path in a grid from start to finish." -> Use BFS. Since each cell transition is unweighted, BFS guarantees shortest distance paths.

"Clone a graph." -> Either DFS or BFS works. Use a visited map mapping originalNode -> clonedNode to avoid cyclic loops.

Common Mistakes

> 2. BFS Visited Flag Timing: Marking nodes as visited after popping from the queue instead of before pushing. In BFS, you must mark a node as visited as soon as you push it onto the queue. Otherwise, a node might be pushed multiple times by different neighbors, leading to duplicate queue additions.

---

7. Summary

DFS: Stack-based, explores deep paths first. Time: O(V + E), Space: O(V) (for recursive stack).

BFS: Queue-based, explores radial levels. Time: O(V + E), Space: O(V) (for queue).

Shortest Path: BFS guarantees shortest path on unweighted graphs.

---

8. Quiz

Question 1: Why does DFS require less memory than BFS on wide, shallow graphs?

Answer: Because BFS queues up all nodes at a given level. On wide graphs, a level might contain O(V) elements, consuming high queue memory. DFS only stores the current depth path on the recursion stack.

Question 2: What is a 'Connected Component' in an undirected graph?

Answer: A subgraph in which any two vertices are connected to each other by paths, and which is connected to no additional vertices in the rest of the graph.

Question 3: If you run BFS on a tree, what standard tree traversal does it correspond to?

Answer: Level-Order Traversal.

Question 4: True or False: DFS guarantees the shortest path between two nodes in an unweighted cyclic graph.

Answer: False. DFS can take a deep winding path of length 10 instead of a direct edge path of length 1. Only BFS guarantees shortest path under unweighted constraints.

Question 5: How do you identify the number of isolated islands (connected components) using graph traversal?

Answer: Loop through all nodes. If a node is unvisited, launch a DFS/BFS traversal from it to mark all connected vertices, and increment the component counter.