Graphs5 min read

Depth-First Search

Follow one road as far as it goes before backtracking
time: \(O(V+E)\)space: \(O(V)\)

Imagine exploring a new city by picking one road and walking it to the very end — then backing up and trying the next road, and so on. You commit fully to each path before exploring alternatives. That's Depth-First Search (DFS).

Unlike BFS which spreads outward in rings, DFS plunges as deep as possible, then backtracks when it hits a dead end (a city with no unvisited neighbors).

Stack (or recursion)

DFS uses a stack — either explicitly or via the call stack of a recursive function. Cities are pushed when discovered and popped when their exploration is done. Recursion is the natural way to write DFS:

pseudocode
1
2
3
4
5
6
7
function dfs(graph, city, visited = new Set()):
  visited.add(city)
  process(city)


  for neighbor of graph[city]:
    if neighbor not in visited:
      dfs(graph, neighbor, visited)

The iterative version replaces the call stack with an explicit stack data structure — useful when recursion depth could overflow.

Finding connected components

A map might have isolated islands — groups of cities with no roads between them. Run DFS from any unvisited city: every city you reach is in the same connected component (you can also track components with Union-Find). After DFS finishes, pick the next unvisited city and start a new DFS. Count how many times you restart to count components.

Cycle detection

During DFS, if you encounter a neighbor that's already been visited (and isn't your direct parent in the DFS tree), you've found a cycle — a circular route on the map. This is essential for detecting deadlocks, validating DAGs (used in topological sort), and more.

pseudocode
1
2
3
4
5
6
7
8
9
10
// For directed graphs, track three states:
// WHITE = unvisited, GRAY = in current path, BLACK = done
function hasCycle(graph, city, color):
  color[city] = GRAY
  for neighbor of graph[city]:
    if color[neighbor] === GRAY: return true  // back edge = cycle!
    if color[neighbor] === WHITE:
      if hasCycle(graph, neighbor, color): return true
  color[city] = BLACK
  return false
◈ Watch DFS explore

← → arrow keys to step · click elements to interact

DFS Traversal (Recursive & Iterative)

graph = {0:[1,2], 1:[0,3,4], 2:[0], 3:[1], 4:[1]}


# Recursive DFS
def dfs_recursive(node, visited=None):
    if visited is None: visited = set()
    visited.add(node)
    result = [node]
    for neighbor in graph[node]:
        if neighbor not in visited:
            result += dfs_recursive(neighbor, visited)
    return result


# Iterative DFS
def dfs_iterative(start):
    visited = set()
    stack = [start]
    result = []
    while stack:
        node = stack.pop()
        if node in visited: continue
        visited.add(node); result.append(node)
        for neighbor in reversed(graph[node]):
            if neighbor not in visited: stack.append(neighbor)
    return result


print(dfs_recursive(0))  # [0, 1, 3, 4, 2]
print(dfs_iterative(0))  # [0, 1, 3, 4, 2]
Output
[0, 1, 3, 4, 2]
[0, 1, 3, 4, 2]
Note: DFS does not guarantee shortest paths. It's best for exhaustive exploration tasks: connected components, cycle detection, topological sorting, and maze solving.

Complexity

Time
Each city and road visited exactly once
Linear \(O(V+E)\)
Space
Call stack or explicit stack holds up to V frames
Linear \(O(V)\)

DFS: Count Islands

def count_islands(grid):
    rows, cols = len(grid), len(grid[0])
    visited = set()


    def dfs(r, c):
        if (r,c) in visited or r<0 or r>=rows or c<0 or c>=cols or grid[r][c]=='0':
            return
        visited.add((r,c))
        for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
            dfs(r+dr, c+dc)


    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c]=='1' and (r,c) not in visited:
                dfs(r, c)
                count += 1
    return count


grid = [
    ['1','1','0','0','0'],
    ['1','1','0','0','0'],
    ['0','0','1','0','0'],
    ['0','0','0','1','1']
]
print(count_islands(grid))  # 3
Output
3
Challenge

Quick check

What data structure mirrors the recursive call stack in an iterative DFS implementation?

Continue reading