DSA course menu
Depth-First Search (DFS) in Python: Recursive and Iterative
Learn depth-first search: recursive and stack-based DFS, connected components, counting islands in a grid, detecting cycles in undirected and directed graphs, and when to choose DFS over BFS.
On this page
Depth-first search (DFS) follows one path as far as it can go, and only when it hits a dead end does it backtrack to the last vertex with unexplored neighbours. It is like exploring a maze by always taking the next unexplored corridor and retracing your steps when stuck.
DFS uses a stack, either the call stack (recursion) or an explicit one.
Recursive DFS#
graph = {
"A": ["B", "C"],
"B": ["A", "D", "E"],
"C": ["A", "F"],
"D": ["B"],
"E": ["B", "F"],
"F": ["C", "E"],
}
def dfs(graph, vertex, visited=None, order=None):
if visited is None:
visited, order = set(), []
visited.add(vertex)
order.append(vertex)
for nxt in graph[vertex]:
if nxt not in visited:
dfs(graph, nxt, visited, order)
return order
print(dfs(graph, "A"))['A', 'B', 'D', 'E', 'F', 'C']Compare with BFS on the same graph, which gives A, B, C, D, E, F: DFS dives from B down to D, back up, into E, and through E reaches F before ever visiting C.
Like BFS, DFS is O(V + E) time. Its space is O(V) for the visited set plus the stack, which can be as deep as the longest path.
Iterative DFS with a stack#
Recursion is limited to about 1000 levels in Python. An explicit stack has no such limit:
graph = {
"A": ["B", "C"],
"B": ["A", "D", "E"],
"C": ["A", "F"],
"D": ["B"],
"E": ["B", "F"],
"F": ["C", "E"],
}
def dfs_iterative(graph, start):
visited, order = set(), []
stack = [start]
while stack:
vertex = stack.pop()
if vertex in visited:
continue
visited.add(vertex)
order.append(vertex)
for nxt in reversed(graph[vertex]): # so the first neighbour is popped first
if nxt not in visited:
stack.append(nxt)
return order
print(dfs_iterative(graph, "A"))['A', 'B', 'D', 'E', 'F', 'C']Connected components#
Start a DFS from every vertex that has not been visited yet; each start discovers one connected component (a group of vertices that can reach each other):
graph = {
1: [2], 2: [1, 3], 3: [2],
4: [5], 5: [4],
6: [],
}
def components(graph):
visited, groups = set(), []
for start in graph:
if start in visited:
continue
group, stack = [], [start]
visited.add(start)
while stack:
v = stack.pop()
group.append(v)
for nxt in graph[v]:
if nxt not in visited:
visited.add(nxt)
stack.append(nxt)
groups.append(sorted(group))
return groups
print(components(graph))[[1, 2, 3], [4, 5], [6]]Counting islands#
In a grid of land (1) and water (0), an island is a group of land cells connected up, down, left or right. Each time you find unvisited land, count an island and flood-fill it with DFS so it is not counted again:
def count_islands(grid):
grid = [row[:] for row in grid] # do not change the caller's grid
rows, cols = len(grid), len(grid[0])
def sink(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols or grid[r][c] != 1:
return
grid[r][c] = 0 # mark as visited
sink(r + 1, c); sink(r - 1, c); sink(r, c + 1); sink(r, c - 1)
islands = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == 1:
islands += 1
sink(r, c)
return islands
world = [
[1, 1, 0, 0, 0],
[1, 1, 0, 0, 1],
[0, 0, 1, 0, 1],
[0, 0, 0, 1, 1],
]
print(count_islands(world))3The cell at row 2, column 2 is its own island: it only touches the others diagonally.
Detecting a cycle#
Undirected graph: during DFS, finding a visited neighbour that is not the vertex you just came from means there is a cycle.
Directed graph: track three states. A vertex is "in progress" while its DFS call is running. Reaching an in-progress vertex means you followed edges back into your own current path: a cycle.
def has_cycle_directed(graph):
WHITE, GREY, BLACK = 0, 1, 2 # unvisited, in progress, done
state = {v: WHITE for v in graph}
def visit(v):
state[v] = GREY
for nxt in graph[v]:
if state[nxt] == GREY:
return True # back edge: a cycle
if state[nxt] == WHITE and visit(nxt):
return True
state[v] = BLACK
return False
return any(state[v] == WHITE and visit(v) for v in graph)
courses = {"intro": ["dsa"], "dsa": ["ml"], "ml": []}
circular = {"a": ["b"], "b": ["c"], "c": ["a"]}
print(has_cycle_directed(courses), has_cycle_directed(circular))False TrueThis is the check behind "these prerequisites are impossible to satisfy" and build tools that refuse circular dependencies. Topological sort builds on it.
DFS or BFS?#
Common mistakes#
Practice#
Practice exercise
Write all_paths(graph, start, goal) that returns every path from start to goal in a directed acyclic graph.
Show hint
DFS while carrying the current path. When you reach goal, save a copy of the path. Since the graph has no cycles, you do not need a visited set.
Show solution
def all_paths(graph, start, goal):
paths = []
def explore(v, path):
if v == goal:
paths.append(path)
return
for nxt in graph[v]:
explore(nxt, path + [nxt])
explore(start, [start])
return paths
graph = {0: [1, 2], 1: [3], 2: [3, 4], 3: [4], 4: []}
for p in all_paths(graph, 0, 4):
print(p)[0, 1, 3, 4]
[0, 2, 3, 4]
[0, 2, 4]Key takeaway#
Next: ordering tasks that depend on each other, with Topological Sort.
Finished this lesson?