DFS — Depth-First Search

Go Deep, Then Backtrack

CS205 Data Structures

Use arrow keys or buttons to navigate

What is DFS?

Explore as deep as possible, then backtrack

Click any node as source. Watch DFS go deep then backtrack.

Click a node to start DFS...

Analogy: Maze Explorer

Always walk forward, taking the first available turn. When you hit a dead end, backtrack to the last intersection and try a different path.

Key Idea

DFS is driven by a stack (either the call stack via recursion, or an explicit stack). It visits vertices in a deep-first manner, not level-by-level.

DFS Uses a Stack (or Recursion)

Two equivalent approaches — toggle to compare

Key Insight

Recursive DFS uses the program's call stack implicitly. Iterative DFS uses an explicit Stack data structure. Both do the same thing!

Stack Overflow Risk

Recursive DFS can overflow on deep graphs (100K+ nodes). The iterative version uses heap memory, avoiding this limit.

DFS Algorithm (Recursive)

Code synced with Canvas — watch the recursion tree build

DFS(G):
  for each vertex v in G:
    visited[v] = false
 
  for each vertex v in G:
    if not visited[v]:
      DFS-Visit(v)
 
DFS-Visit(u):
  visited[u] = true
  // process u
 
  for each neighbor v of u:
    if not visited[v]:
      DFS-Visit(v)  // recurse!

How It Works

Mark current vertex as visited
Recurse on each unvisited neighbor
When all neighbors visited, return (backtrack)
Outer loop handles disconnected graphs

Key Idea

The recursion tree of DFS-Visit calls IS the DFS tree of the graph.

DFS Algorithm (Iterative)

Explicit stack — watch push/pop operations

DFS-Iterative(G, source):
  S = new Stack()
  S.push(source)
 
  while S is not empty:
    u = S.pop()
 
    if u not in visited:
      visited.add(u)
      // process u
 
      for each neighbor v of u:
        if v not in visited:
          S.push(v)

Stack: []

BFS vs DFS: One Character Difference

Replace the Stack with a Queue, and you get BFS! That's the only structural difference.

Subtle Difference

Iterative DFS may visit in a different order than recursive, because it pushes ALL neighbors at once. Recursive visits one neighbor completely before looking at the next.

DFS Step-by-Step Walkthrough

7-node graph — watch the stack, visited set, and DFS tree build live

Call Stack: []

Visited: {}

DFS Tree edges shown in green. Current vertex in amber. Backtracking shown in yellow.

DFS Tree & Edge Classification

Every edge in a directed graph falls into one of four categories

Edge Type	Goes To	Color
Tree	Unvisited (WHITE)	GREEN
Back	Ancestor (GRAY) → CYCLE!	AMBER
Forward	Descendant (BLACK, d[u]	BLUE
Cross	Neither (BLACK, d[u]>d[v])	PURPLE

Undirected Graphs

In undirected graphs, only tree edges and back edges exist. Forward and cross edges cannot occur.

Key Rule

Back edge = CYCLE. This is the foundation of DFS-based cycle detection.

Discovery & Finish Times

DFS assigns two timestamps: d[v] (discovery) and f[v] (finish)

Parenthesis Theorem

For any two vertices u, v: their intervals [d[u],f[u]] and [d[v],f[v]] are either entirely disjoint or one completely contains the other. They never partially overlap — like properly nested parentheses!

Nested Boxes

Each vertex is a box that opens at d[v] and closes at f[v]. Boxes are completely inside each other or completely separate.

BFS vs DFS Comparison

Same graph, different exploration — toggle to compare

Property	BFS	DFS
Data structure	Queue (FIFO)	Stack (LIFO)
Exploration	Level by level	Deep first
Shortest path?	Yes (unweighted)	No
Cycle detection	Possible	Natural
Topological sort	No	Yes
Time	O(V+E)	O(V+E)

Edge Classification via Colors

WHITE → GRAY → BLACK vertex states determine edge types

// When exploring edge u → v:
if color[v] == WHITE:
    // Tree edge
if color[v] == GRAY:
    // Back edge (CYCLE!)
if color[v] == BLACK:
    if d[u] < d[v]: // Forward
    else:            // Cross

The Critical Rule

Edge to a GRAY vertex = ancestor still being processed = CYCLE!

Cycle Detection with DFS

Toggle directed (3-color) vs undirected (parent-check)

dfsDetect(u):
  color[u] = GRAY
  for each neighbor v of u:
    if color[v] == GRAY:
      return true  // CYCLE!
    if color[v] == WHITE:
      if dfsDetect(v): return true
  color[u] = BLACK
  return false

Undirected Caveat

Every undirected edge appears twice (u-v and v-u). Exclude the parent edge when checking for back edges.

Topological Sort

Linear ordering where u comes before v for every edge u → v

Finish stack: []

Topo order: (run DFS)

Key Idea

Topological sort = reverse of DFS finish order. When a vertex finishes (all descendants explored), prepend it to the result.

Prerequisite

Only works on DAGs (Directed Acyclic Graphs). If there's a cycle, no valid topological order exists!

Connected Components (Undirected)

Each DFS call from the outer loop discovers one full component

connectedComponents(G):
  comp = 0
  for each vertex v in G:
    if v not visited:
      dfs(v, comp)  // new component!
      comp += 1

Key Idea

Number of outer-loop DFS calls = number of connected components.

Strongly Connected Components (Directed)

Kosaraju's Algorithm: DFS → Reverse → DFS again

Phase 1: DFS on original graph

Kosaraju's Algorithm

Run DFS on G, record finish times
Compute G^T (reverse all edges)
Run DFS on G^T in decreasing finish time
Each DFS tree in step 3 = one SCC

Analogy

SCCs are "islands" where you can travel between any two cities. Kosaraju finds them by looking at the graph forwards AND backwards.

Maze Generation & Solving

DFS creates long winding corridors — perfect for mazes

DFS Maze Generation

Start at a cell, pick a random unvisited neighbor, remove the wall between them. When stuck, backtrack. This creates a "perfect maze" — exactly one path between any two cells.

Time & Space Complexity

O(V + E) time, O(V) space — same as BFS

Vertex visits: 0 | Edge checks: 0

Representation	DFS Time	Space
Adjacency List	O(V + E)	O(V)
Adjacency Matrix	O(V²)	O(V)

Why O(V + E)?

Each vertex visited once (O(V)). Each edge checked once per direction (O(E)). Total = O(V + E).

Stack Depth

Worst case: path graph → stack depth = V. This can cause stack overflow with recursion on deep graphs!

Challenge: Predict the DFS Order

Given this graph and source A (recursive DFS, alphabetical neighbors), what's the visit order?

Undirected graph. Neighbors in alphabetical order. Source = A.

Type the DFS visit order (comma-separated):

Challenge: Fix the Bug

This iterative DFS has a subtle bug — can you find it?

DFS-Iterative(G, source):
  S = new Stack()
  S.push(source)
  
  while S is not empty:
    u = S.pop()
    visited[u] = true  // always mark
    process(u)
    for each neighbor v of u:
      S.push(v)  // push ALL neighbors!

What's wrong with this code?

Challenge: BFS or DFS?

Pick the best algorithm for each scenario

1. Find if there's a circular dependency in a build system (DAG check).

2. Find the minimum number of hops between two routers in a network.

3. Determine a valid course schedule that respects all prerequisites.

4. Count the number of connected components in an undirected graph.

Summary & Cheat Sheet

Everything you need to know about DFS

Core Applications

Cycle detection — back edge = cycle
Topological sort — reverse finish order
Connected components (undirected)
SCCs — Kosaraju / Tarjan
Path finding & backtracking
Maze generation and solving

Common Pitfalls

Iterative DFS: missing visited check → infinite loop on cycles
Recursive DFS: stack overflow on deep graphs
Using DFS for shortest path (use BFS instead!)
Undirected cycle detection: forgetting to exclude parent edge

Property	DFS	BFS
Data structure	Stack	Queue
Shortest path?	No	Yes
Topological sort?	Yes	No
Time	O(V+E)	O(V+E)
Space	O(V)	O(V)

Quiz: Test Your DFS Knowledge

3 questions — check your answers when ready

Q1: What does a back edge in DFS indicate?

A shorter path exists A cycle exists The graph is disconnected A vertex was visited twice

Q2: How do you get topological sort from DFS?

Visit order as-is Reverse of discovery order Reverse of finish order Sorted by degree

Q3: What color means "in progress" in 3-color DFS?

WHITE GRAY BLACK RED

Trace: DFS with Timestamps

Step through DFS on this directed graph, track d[v] and f[v]

Edge Classification via Timestamps

Tree/Forward: d[u] < d[v] < f[v] < f[u]
Back: d[v] < d[u] < f[u] < f[v]
Cross: d[v] < f[v] < d[u] < f[u]

Predict the Output

What does this Java DFS code print?

// Graph: 0→1, 0→2, 1→3, 2→3, 3→4
// Adjacency list, neighbors in order
boolean[] visited = new boolean[5];
List<Integer> order = new ArrayList<>();
List<Integer> finish = new ArrayList<>();
 
void dfs(int u) {
  visited[u] = true;
  order.add(u);
  for (int v : adj[u]) {
    if (!visited[v]) dfs(v);
  }
  finish.add(u);
}
 
dfs(0);
System.out.println(order);
System.out.println(finish);

What is the visit order (order list)?

What is the finish order (finish list)?

DFS — Depth-First Search

What is DFS?

Analogy: Maze Explorer

Key Idea

DFS Uses a Stack (or Recursion)

Key Insight

Stack Overflow Risk

DFS Algorithm (Recursive)

How It Works

Key Idea

DFS Algorithm (Iterative)

BFS vs DFS: One Character Difference

Subtle Difference

DFS Step-by-Step Walkthrough

DFS Tree & Edge Classification

Undirected Graphs

Key Rule

Discovery & Finish Times

Parenthesis Theorem

Nested Boxes

BFS vs DFS Comparison

Edge Classification via Colors

The Critical Rule

Cycle Detection with DFS

Undirected Caveat

Topological Sort

Key Idea

Prerequisite

Connected Components (Undirected)

Key Idea

Strongly Connected Components (Directed)

Kosaraju's Algorithm

Analogy

Maze Generation & Solving

DFS Maze Generation

DFS Maze Solving

Time & Space Complexity

Why O(V + E)?

Stack Depth

Challenge: Predict the DFS Order

Challenge: Fix the Bug

The Fix

Challenge: BFS or DFS?

Summary & Cheat Sheet

Core Applications

Common Pitfalls

Quiz: Test Your DFS Knowledge

Trace: DFS with Timestamps

Edge Classification via Timestamps

Predict the Output