Depth-First Search on a Graph in Python

Preamble

DFS is the backbone of many easy–medium graph problems (topic plan algorithms track): connectivity, cycle detection with coloring, exhaustive search. Here are recursive and stack-based variants on an adjacency list—same algorithm, different stack discipline.

Adjacency list DFS

def dfs_rec(graph, start, visited=None):
    if visited is None:
        visited = set()
    visited.add(start)
    for nbr in graph.get(start, ()):
        if nbr not in visited:
            dfs_rec(graph, nbr, visited)
    return visited

def dfs_iter(graph, start):
    seen, stack = set(), [start]
    while stack:
        v = stack.pop()
        if v in seen:
            continue
        seen.add(v)
        stack.extend(graph.get(v, ()))
    return seen

Order may differ between versions—document whether pre-order matters for your problem.

Debugging and stack depth

Recursion reads cleanly for small graphs; iterative DFS avoids RecursionError on deep chains. Single-step debugging is often easier on the explicit stack variant.

Conclusion

Time O(V + E), space O(V) for visited plus stack/recursion. Pick the version you can explain under pressure. Breadth-First Search and Shortest Path Layers in Python covers BFS and deque.