Depth-first search

Follow one path as far as it goes, then backtrack — the traversal behind cycle detection, topological sort and maze solving.

Complexity: O(V + E) time · O(V) space

The idea

Depth-first search commits: from the current node it picks a neighbour and immediately explores from there, going deeper and deeper until it hits a node with no unvisited neighbours. Only then does it back up and try the next option.

A visited set is the whole trick. Marking a node before exploring it means every node is expanded at most once, so cycles can't trap the search.

Why recursion fits

The call stack remembers the path back for free — each recursive call is one step deeper, and returning from a call is the backtrack. An explicit stack does the same job iteratively when recursion depth is a concern.

Watch for it on the canvas

Run the code against a dense graph and watch the highlight dive along a single path, then rewind through the recursion to pick up branches it skipped. That deep-then-backtrack rhythm is the signature of DFS.

Try it on this graph:

# Depth-first search from node "A" — the canvas animates on its own
# as the algorithm reads the graph through graph.getNeighbors().
visited = set()

def dfs(node):
    if node in visited:
        return
    visited.add(node)
    print(node)
    for neighbour in graph.getNeighbors(node):
        dfs(neighbour)

dfs("A")

Open this post in a project to run it and step through every decision.