Depth-First Traversal and Breadth-First Traversal

[qingquan-li]

Example Graph

Consider the following graph, which we'll use for demonstrating DFS and BFS:

    1
   / \
  2   3
 /   / \
4   5   6

• Node 1 is connected to nodes 2 and 3.
• Node 2 is connected to node 4.
• Node 3 is connected to nodes 5 and 6.

Depth-First Traversal (DFS)

DFS explores as far as possible down one path before backtracking.

DFS Steps:

1. Start at node 1.
2. Visit node 2.
3. Visit node 4, the child of node 2. (No more children, backtrack to node 2, then to node 1)
4. Visit node 3.
5. Visit node 5, the child of node 3.
6. Visit node 6, the other child of node 3.

DFS Traversal Order: 1, 2, 4, 3, 5, 6

Breadth-First Traversal (BFS)

BFS explores the neighbor nodes first before going to the next level of nodes.

BFS Steps:

1. Start at node 1.
2. Visit nodes 2 and 3, the neighbors of node 1.
3. Visit node 4, the child of node 2.
4. Visit nodes 5 and 6, the children of node 3.

BFS Traversal Order: 1, 2, 3, 4, 5, 6

Visualization in Graph Form

• DFS Path: The DFS path would show a deep dive from node 1 to 2 to 4, then backtrack to 1, and then to 3, 5, and finally 6.
• BFS Path: The BFS path would show an exploration from node 1 to its immediate neighbors 2 and 3, then to node 4 (which is 2's neighbor), and finally to nodes 5 and 6 (which are 3's neighbors).

These examples demonstrate how DFS explores as deeply as possible into each branch before backtracking, while BFS explores all neighbors at the current depth level before moving to the next level. DFS is often implemented using recursion or a stack, while BFS is typically implemented using a queue.