Depth first search in Python follows one branch of a graph as far as it can go, then backs up and tries the next branch. A short recursive function and a set of visited nodes is all it takes:
def dfs(graph, node, visited):
visited.add(node)
for nxt in graph[node]:
if nxt not in visited:
dfs(graph, nxt, visited)
The graphs here are things you’d actually model, like course prerequisites and service dependencies, and each script ran on Python 3.12.5.
We’ll build recursive and stack-based DFS, list every path, detect cycles, produce a topological order, count islands on a grid, and handle Python’s recursion limit.
Recursive depth first search in Python
This graph maps each course to the courses it unlocks. Starting from Intro to Python, DFS dives down the first branch all the way to Machine Learning before it comes back for Web Basics:
prereqs = {
"Intro to Python": ["Data Structures", "Web Basics"],
"Data Structures": ["Algorithms", "Databases"],
"Web Basics": ["Flask Apps"],
"Algorithms": ["Machine Learning"],
"Databases": ["Flask Apps", "Machine Learning"],
"Flask Apps": [],
"Machine Learning": [],
}
def dfs(graph, node, visited=None):
if visited is None:
visited = []
visited.append(node)
for nxt in graph[node]:
if nxt not in visited:
dfs(graph, nxt, visited) # go deep before trying the next sibling
return visited
for i, course in enumerate(dfs(prereqs, "Intro to Python"), start=1):
print(i, course)
Output:
1 Intro to Python
2 Data Structures
3 Algorithms
4 Machine Learning
5 Databases
6 Flask Apps
7 Web Basics

Compare that with breadth first search, which would visit Data Structures and Web Basics first because they’re one step away.
Iterative DFS with a stack
Recursion uses Python’s call stack behind the scenes. You can manage your own list as a stack instead, which avoids the recursion limit on very deep graphs:
prereqs = {
"Intro to Python": ["Data Structures", "Web Basics"],
"Data Structures": ["Algorithms", "Databases"],
"Web Basics": ["Flask Apps"],
"Algorithms": ["Machine Learning"],
"Databases": ["Flask Apps", "Machine Learning"],
"Flask Apps": [],
"Machine Learning": [],
}
def dfs_stack(graph, start):
visited, stack = [], [start]
while stack:
node = stack.pop() # last in, first out
if node in visited:
continue
visited.append(node)
stack.extend(reversed(graph[node])) # reversed keeps the same order as recursion
return visited
print(dfs_stack(prereqs, "Intro to Python"))
Output:
['Intro to Python', 'Data Structures', 'Algorithms', 'Machine Learning', 'Databases', 'Flask Apps', 'Web Basics']
Pushing the neighbors in reverse makes the stack pop them in their original order, so the output matches the recursive version exactly.
Finding all paths between two nodes with DFS
Because DFS explores one complete route at a time, it’s a natural fit for listing every path. Track the current path and skip nodes already on it:
prereqs = {
"Intro to Python": ["Data Structures", "Web Basics"],
"Data Structures": ["Algorithms", "Databases"],
"Web Basics": ["Flask Apps"],
"Algorithms": ["Machine Learning"],
"Databases": ["Flask Apps", "Machine Learning"],
"Flask Apps": [],
"Machine Learning": [],
}
def all_paths(graph, start, goal, path=()):
path = path + (start,)
if start == goal:
return [path]
found = []
for nxt in graph[start]:
if nxt not in path:
found += all_paths(graph, nxt, goal, path)
return found
for p in all_paths(prereqs, "Intro to Python", "Machine Learning"):
print(" -> ".join(p))
Output:
Intro to Python -> Data Structures -> Algorithms -> Machine Learning
Intro to Python -> Data Structures -> Databases -> Machine Learning
I’d expect this to explode on large, dense graphs, since the number of paths can grow very fast. For just the shortest path, use BFS.
How do you detect a cycle with DFS?
Color each node: white for unvisited, gray while its branch is being explored, black when finished. Reaching a gray node again means you’ve looped back, so there’s a cycle:
def find_cycle(graph):
WHITE, GRAY, BLACK = 0, 1, 2 # unvisited, in progress, finished
color = {n: WHITE for n in graph}
stack = []
def visit(node):
color[node] = GRAY
stack.append(node)
for nxt in graph[node]:
if color[nxt] == GRAY: # back to a node still in progress
return stack[stack.index(nxt):] + [nxt]
if color[nxt] == WHITE:
cycle = visit(nxt)
if cycle:
return cycle
stack.pop()
color[node] = BLACK
return None
for n in graph:
if color[n] == WHITE:
cycle = visit(n)
if cycle:
return cycle
return None
ok = {"api": ["db", "auth"], "auth": ["db"], "db": []}
bad = {"api": ["auth"], "auth": ["billing"], "billing": ["api"]}
print("ok: ", find_cycle(ok))
print("bad:", " -> ".join(find_cycle(bad)))
Output:
ok: None
bad: api -> auth -> billing -> api

api, which is exactly the kind of circular dependency build tools reject.Topological sort using depth first search
If a graph has no cycles, DFS can order its nodes so every prerequisite comes first. Add each node after its descendants finish, then reverse the list:
prereqs = {
"Intro to Python": ["Data Structures", "Web Basics"],
"Data Structures": ["Algorithms", "Databases"],
"Web Basics": ["Flask Apps"],
"Algorithms": ["Machine Learning"],
"Databases": ["Flask Apps", "Machine Learning"],
"Flask Apps": [],
"Machine Learning": [],
}
from graphlib import TopologicalSorter
def topo_sort(graph):
seen, order = set(), []
def visit(node):
if node in seen:
return
seen.add(node)
for nxt in graph[node]:
visit(nxt)
order.append(node) # added after everything that depends on it
for node in graph:
visit(node)
return order[::-1]
plan = topo_sort(prereqs)
print("take in this order:")
for i, c in enumerate(plan, 1):
print(f" {i}. {c}")
# graphlib wants "node: things it depends on", so flip the edges to check
needs = {c: [p for p, nxts in prereqs.items() if c in nxts] for c in prereqs}
order = list(TopologicalSorter(needs).static_order())
print("valid per graphlib:", all(order.index(p) < order.index(c) for p in prereqs for c in prereqs[p]))
print("our plan valid too:", all(plan.index(p) < plan.index(c) for p in prereqs for c in prereqs[p]))
Output:
take in this order:
1. Intro to Python
2. Web Basics
3. Data Structures
4. Databases
5. Flask Apps
6. Algorithms
7. Machine Learning
valid per graphlib: True
our plan valid too: True

For production code, Python’s built-in graphlib.TopologicalSorter does this for you and raises CycleError on loops. I still think writing it yourself once is the best way to understand it.
Counting islands on a grid with DFS
Grids are graphs too. Each time you find an unvisited land cell, a DFS “sinks” the whole connected island, so the number of DFS starts is the number of islands:
grid = [
"11000110",
"11000100",
"00100000",
"00011011",
]
def count_islands(grid):
rows, cols = len(grid), len(grid[0])
seen = set()
def sink(r, c):
if not (0 <= r < rows and 0 <= c < cols) or grid[r][c] == "0" or (r, c) in seen:
return 0
seen.add((r, c))
return 1 + sink(r + 1, c) + sink(r - 1, c) + sink(r, c + 1) + sink(r, c - 1)
sizes = [sink(r, c) for r in range(rows) for c in range(cols)
if grid[r][c] == "1" and (r, c) not in seen]
return sizes
sizes = count_islands(grid)
print(len(sizes), "islands, sizes:", sizes)
Output:
5 islands, sizes: [4, 3, 1, 2, 2]

The same flood-fill idea powers the paint-bucket tool in image editors. Storing the grid as a list of lists lets you mark cells in place instead of using a set.
RecursionError in recursive DFS and how to avoid it
CPython limits recursion depth to about 1,000 calls by default. A long chain of nodes blows past that with recursive DFS:
import sys
chain = {i: [i + 1] for i in range(5000)}
chain[5000] = []
def depth(graph, node):
return 1 + max((depth(graph, n) for n in graph[node]), default=0)
print("recursion limit:", sys.getrecursionlimit())
try:
depth(chain, 0)
except RecursionError as err:
print("RecursionError:", err)
Output:
recursion limit: 1000
RecursionError: maximum recursion depth exceeded
You can raise the limit with sys.setrecursionlimit(), but I’d reach for the iterative stack version instead; it’s the safer fix. Recursion in Python explains why the limit exists.
DFS vs BFS
| Depth first search | Breadth first search | |
|---|---|---|
| Data structure | Stack or recursion | Queue (deque) |
| Order | Deep along one branch first | Level by level |
| Best for | Cycles, topological sort, all paths, flood fill | Shortest path in unweighted graphs |
| Memory | Grows with depth | Grows with width |
| Time | O(V + E) | O(V + E) |
Want more algorithm practice? Try these:
- Breadth first search in Python
- Binary tree in Python
- Sorting algorithms in Python
- Binary search in Python
Frequently asked questions
What is depth first search in Python?
It’s a graph traversal that goes as deep as possible along each branch before backtracking, written with recursion or an explicit stack.
Is DFS recursive or iterative?
Either. Recursion is shorter; an explicit stack avoids the recursion limit on deep graphs.
What is DFS used for?
Cycle detection, topological sorting, finding connected components, maze generation, and listing all paths.