Depth-first search

Applies to: general, python

Depth-first search explores a graph by going as deep as possible along one branch before backtracking, usually written with recursion or a stack. It suits path finding, cycle detection, and exploring whole subtrees.

def dfs(node, seen):
    seen.add(node)
    for nb in adj[node]:
        if nb not in seen:
            dfs(nb, seen)

See also: breadth-first-search, recursion