Depth First Search in Python (DFS with Examples)

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
Command Prompt output of a recursive depth first search in Python over a graph of course prerequisites
DFS finishes the whole Data Structures branch before it ever visits 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
Command Prompt output of Python DFS cycle detection finding no cycle in one dependency graph and api to auth to billing to api in another
The second graph loops back to 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
Command Prompt output of a DFS topological sort of course prerequisites, verified against Python's graphlib TopologicalSorter
Both orders put every prerequisite before the courses that need it.

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]
Command Prompt output of a Python depth first search flood fill counting islands of 1s on a grid with their sizes
Each DFS returns how many cells it sank, which gives you island sizes for free.

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 searchBreadth first search
Data structureStack or recursionQueue (deque)
OrderDeep along one branch firstLevel by level
Best forCycles, topological sort, all paths, flood fillShortest path in unweighted graphs
MemoryGrows with depthGrows with width
TimeO(V + E)O(V + E)

Want more algorithm practice? Try these:

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.

Does DFS find the shortest path?