DFS Theory

Definition

Given a graph G = (V, E), DFS explores edges out of the most recently discovered vertex that still has unexplored neighbors. It produces a depth-first forest of rooted trees capturing parent relationships of the traversal.

Algorithm Steps

1. Initialize all vertices WHITE (undiscovered), parent NIL.
2. Iterate vertices; for each WHITE vertex start a DFS-Visit.
3. Mark vertex GRAY upon discovery (active in recursion stack).
4. Recursively visit each WHITE neighbor, setting parent.
5. After exploring neighbors, mark vertex BLACK and assign finish time.
6. Repeat until all vertices processed; forest may have multiple trees.

Time & Space Complexity

Each vertex discovered and finished once; each edge examined at most twice (undirected) or once (directed).

Pseudocode

1DFS(G):
2  for each vertex v in G:
3    color[v] ← WHITE
4    parent[v] ← NIL
5  time ← 0
6  for each vertex v in G:
7    if color[v] = WHITE:
8      DFS-Visit(G, v)
9 
10DFS-Visit(G, u):
11  color[u] ← GRAY
12  time ← time + 1
13  discover[u] ← time
14  for each neighbor v of u:
15    if color[v] = WHITE:
16      parent[v] ← u
17      DFS-Visit(G, v)
18  color[u] ← BLACK
19  time ← time + 1
20  finish[u] ← time

Applications

• Topological sorting
• Detect cycles (back edges)
• Find articulation points & bridges
• Compute strongly connected components (Kosaraju/Tarjan)
• Maze/path generation & solving variants

Advantages & Disadvantages

Example Problems

• Order tasks with dependencies (topological sort)
• Detect cycles in course prerequisite graph
• Enumerate connected components
• Identify articulation points in a network
• Compute strongly connected components