Skip to content
Tutorials Center
My learning

Topics

Lesson 12 of 36 ยท Connectivity and Paths

Depth-First Search

Learn depth-first search: recursive and iterative Python versions, discovery and finish times, edge classification, cycle detection and topological sorting of directed acyclic graphs.

If BFS is a ripple spreading outward, depth-first search (DFS) is a curious explorer in a cave: go down one tunnel as far as it goes, and only when you hit a dead end, back up to the last junction and try the next tunnel. DFS uses a stack (explicit, or the recursion call stack) instead of a queue.

DFS does not give shortest paths, but it reveals the structure of a graph: cycles, components, ordering of tasks, and much more. Its running time is O(n + m) on an adjacency list, the same as BFS.

Recursive DFS

TEXT
dfs(u):
    mark u visited
    for each neighbor w of u:
        if w not visited:
            parent[w] = u
            dfs(w)
Python Recursive DFS with timestamps

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Each vertex gets a discovery time and a finish time. The intervals [discover, finish] of two vertices are either nested or disjoint, never partially overlapping (the "parenthesis structure"). A vertex v lies below u in the DFS tree exactly when v's interval is nested inside u's.

Iterative DFS

Python limits recursion depth (about 1000 by default), so for big graphs write DFS with an explicit stack:

Python Iterative DFS

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Note that for iterative DFS we mark vertices visited when we pop them (a vertex may sit on the stack several times); this is the opposite of the BFS rule, and both are correct for their data structure.

Edge classification in directed graphs

During DFS on a directed graph every arc (u, v) is one of four kinds:

  • Tree edge: v was discovered through u.
  • Back edge: v is an ancestor of u still being processed. A back edge means a cycle.
  • Forward edge: v is a finished descendant of u.
  • Cross edge: v is in another, already finished branch.

In an undirected graph there are only tree edges and back edges.

Detecting cycles

A directed graph has a cycle if and only if DFS finds a back edge. We track three colors: white (unvisited), gray (on the current recursion path), black (finished). An arc to a gray vertex is a back edge.

Python Cycle detection in a directed graph

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Topological sort

A topological order of a DAG lists the vertices so every arc goes from an earlier to a later vertex: a valid order to do tasks that depend on each other (compile order, course prerequisites). The beautiful DFS fact: list the vertices in decreasing finish time.

Python Topological sort with DFS

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

BFS or DFS?

Need Use
Shortest path, fewest edges BFS
Cycle detection, topological order DFS
Components, reachability either
Very deep graph without recursion iterative DFS or BFS
Bridges and cut vertices DFS

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. In a directed graph, a back edge found during DFS means:

    A back edge points to an ancestor that is still being explored, closing a directed cycle.
  2. 2. Which valid topological order exists for arcs a->b, a->c, b->d, c->d?

    Every arc must go from an earlier vertex to a later one: a first, d last. (a, c, b, d) works too.
  3. 3. Why prefer an iterative DFS for huge graphs in Python?

    Deep recursion raises RecursionError (default limit about 1000); an explicit stack has no such limit.
  4. 4. What is the running time of DFS on an adjacency list?

    Every vertex is visited once and every edge examined a constant number of times.

Summary

  • DFS goes as deep as possible before backtracking, using recursion or a stack.
  • It runs in O(n + m) and gives discovery and finish times.
  • A directed graph is acyclic exactly when DFS finds no back edge.
  • Decreasing finish time gives a topological order of a DAG.
  • Use iterative DFS to avoid Python's recursion limit.

Next: Connected Components and Cuts