Depth-First Search (DFS) Tutorial

A concise, step-by-step guide to DFS on a simple graph

What is DFS?

• Depth-First Search (DFS) is a graph traversal algorithm.
• It explores as far along a branch as possible before backtracking.
• DFS uses a stack (explicit or recursive call stack) to track nodes.

Why use DFS?

• Cycle detection: Useful for detecting cycles in directed/undirected graphs.
• Topological sorting: Basis of many graph algorithms.
• Pathfinding: Used in maze solving and exhaustive search when path cost isn’t uniform.

Real-world examples

• File systems: Traversing folders and files.
• AI pathfinding: Exploring all possible moves deeply before backtracking.
• Web crawling: Exploring links recursively before returning to parent site.

DFS Pseudocode

DFS(Graph, v):
  mark v as discovered
  for each neighbor w of v:
    if w is not discovered:
      DFS(Graph, w)

Example: Traversing the Graph using DFS

We’ll traverse this 7-node graph starting at node A, using pre-order DFS.

Stack

Step-by-Step DFS Execution

1. Initialization

   • Stack = [A]
   • Visited = ∅

2. Step 1

   • Pop A → Stack = []
   • Visit A → Visited = [A]
   • Push neighbors (C, B) → Stack = [C, B]

3. Step 2

   • Pop B → Stack = [C]
   • Visit B → Visited = [A, B]
   • Push neighbors (E, D) → Stack = [C, E, D]

4. Step 3

   • Pop D → Stack = [C, E]
   • Visit D → Visited = [A, B, D]
   • D has no undiscovered neighbors

5. Step 4

   • Pop E → Stack = [C]
   • Visit E → Visited = [A, B, D, E]
   • E has no undiscovered neighbors

6. Step 5

   • Pop C → Stack = []
   • Visit C → Visited = [A, B, D, E, C]
   • Push neighbors (G, F) → Stack = [G, F]

7. Step 6

   • Pop F → Stack = [G]
   • Visit F → Visited = [A, B, D, E, C, F]
   • F has no undiscovered neighbors

8. Step 7

   • Pop G → Stack = []
   • Visit G → Visited = [A, B, D, E, C, F, G]
   • G has no undiscovered neighbors

All nodes have now been visited.

Final DFS visitation order:

A → B → D → E → C → F → G

Earning Opportunity with AI

Grab Great Deals

Coursera Courses Deal    Get AppSumo Deal

Enjoyed this post?

If this article helped you,
☕ Buy me a coffee
Your support keeps more things coming!