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?
Related lessons
Recommended DSA resources
- Cracking the Coding Interview by Gayle Laakmann McDowell
189 practice questions with solutions, for coding interview preparation.
Some links are affiliate links. If you buy through them, Laviyx Learn may earn a commission at no extra cost to you. As an Amazon Associate, we earn from qualifying purchases.