AlgoVerse

Depth-first search (DFS)

Go as deep as possible along one path from the source, and when stuck, back up and try another way.

Depth-first search goes as far as it can along one path from the source. When the current node has no unseen neighbour left (a dead end), it is finished and DFS backs up one step to try another way from the previous node.

Read the full explanation ↓
Input:
V=6 · E=7 · src=UPDF export

A six-node directed graph with a cycle; DFS from U goes deep, hits a dead end and backs up.

  1. def dfs(graph, src):
  2. seen = set()
  3. parent = {v: None for v in graph}
  4. order = []
  5. visit(graph, src, seen, parent, order)
  6. return order, parent
  9. def visit(graph, u, seen, parent, order):
  10. seen.add(u)
  11. order.append(u)
  12. for v, _ in graph[u]:
  13. if v not in seen:
  14. parent[v] = u
  15. visit(graph, v, seen, parent, order)
  16. return

Invariant: The nodes on the call stack form a path in the DFS tree from the source to the current node.

Start

UVWXYZ
  • Visited
  • Current node (u)
  • Search tree (from parent)
  • Edge being checked

Recursion tree

Filled orange = running call · Orange outline = still on the stack · Grey = finished

Local variables

src'U'

Orange = changed in this step

graph dict
  • 'U': [('V', 1), ('X', 1)]
  • 'V': [('Y', 1)]
  • 'W': [('Y', 1), ('Z', 1)]
  • 'X': [('V', 1)]
  • 'Y': [('X', 1)]
  • 'Z': []

Call stack

  1. dfs()line 1
Step 1 of 42
Black = discover · Orange = key stepdiscover: 0/4 · check: 0/5 · descend: 0/3 · finish: 0/4

    How the work grows with input size

    Average of 5 random graphs per n (fixed seeds). Hollow marker = the input on screen.

    • check
    • discover
    • current input (n=6)
    0204060481216202428n = number of nodescheckdiscover
    Show as a table
    ncheckdiscover
    45.24
    813.88
    1220.812
    162816
    2035.420
    2437.224
    2847.228
    Explanation

    The idea

    Depth-first search goes as far as it can along one path from the source. When the current node has no unseen neighbour left (a dead end), it is finished and DFS backs up one step to try another way from the previous node.

    Recursion does the backing up for free: each visit(u) calls visit(v) for a new neighbour, and when that returns, the work on u continues. So the call stack is exactly the path from the source to the current node.

    The steps

    1. Add u to seen (it is discovered).
    2. For each neighbour v of u: if v is unseen, record parent[v] = u and call visit(v).
    3. When every neighbour has been checked, u is finished; return.

    Cost

    Every node is discovered once and every edge is checked once (twice in an undirected graph): O(V + E). The recursion can be V deep in the worst case; see the "chain" input.

    Uses

    DFS is the basis of many graph algorithms: finding cycles, topological sort, strongly connected components and cut vertices.

    What to watch in the trace

    • Black nodes have been seen, and the orange node is u in the running call.
    • The blue edges are the DFS tree (from parent).
    • The "recursion tree" is exactly the DFS tree: watch the stack grow deep and unwind.
    • Compare BFS and DFS on the same graph: BFS spreads wide, DFS goes deep.