Skip to content
Tutorials Center
My learning

Topics

Lesson 123 of 225 ยท Graphs

Depth-First Search

Learn depth-first search in Python: recursive and iterative versions, discovery and finish times, path finding, applications, and how DFS compares with BFS.

If breadth-first search is ripples in a pond, depth-first search (DFS) is exploring a cave. You walk down one tunnel as far as it goes. At a dead end you back up to the last junction that still has an unexplored branch and try that one. You only come back to the entrance when every tunnel has been explored.

DFS is the engine behind many graph algorithms: finding connected components, detecting cycles, ordering tasks with topological sort, finding bridges and strongly connected components, and solving mazes and puzzles. On trees you already know it as preorder and postorder traversal (tree traversals). On a general graph we add a visited set so cycles cannot trap us.

The idea

TEXT
graph:        0 --- 1 --- 3
              |     |
              2     4
               \   /
                 5 --- 6

DFS from 0, neighbors tried in listed order:

0 -> 1 -> 3        dead end, back up to 1
          1 -> 4 -> 5 -> 2    2's neighbors (0, 5) are both visited, back up
                    5 -> 6    dead end
order: 0 1 3 4 5 2 6

DFS keeps a path of "open" vertices (those still being explored). That path is exactly what a stack holds, and recursion gives you a stack for free: the call stack.

Recursive DFS

The recursive version is the shortest one to write:

  1. Mark the current vertex visited.
  2. For each neighbor that is not visited, call DFS on it.
Python Recursive 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.

Compare this order with BFS from the same start: BFS gave 0 1 2 3 4 5 6 (closest first), while DFS dives and gives 0 1 3 4 5 2 6.

Iterative DFS with an explicit stack

Python limits recursion depth (about 1,000 calls by default), and a graph with a long path, such as a 100,000-vertex chain, will crash the recursive version. The fix is to manage the stack yourself with a list.

The simplest way pushes the start vertex and, at every step, pops a vertex, and if it is new, visits it and pushes all its neighbors. It visits every vertex, but in a different order than the recursive version, because the last neighbor pushed is the first one explored. Push the neighbors in reverse to match the recursive order.

Python Iterative DFS with a stack

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.

Notice that here the visited check happens when we pop, unlike BFS where we mark when we push. With a stack, a vertex can be pushed several times before it is first visited, and the order of visiting must reflect the moment we actually go there. The duplicate entries are harmless: they are skipped on pop.

Both versions are valid DFS orders. A graph usually has many different valid DFS orders, depending on which neighbor you try first. Algorithms built on DFS work with any of them.

Discovery and finish times

DFS gives each vertex two timestamps from a shared counter: the discovery time (when it is first reached) and the finish time (when all of its neighbors are fully explored and we leave it). They nest like parentheses (the table below is the output of the next example): if v is explored while u is open, then v's interval sits entirely inside u's.

TEXT
vertex   discovered  finished   interval
  0           1          14      [1 ................................ 14]
  1           2          13        [2 ............................ 13]
  3           3           4          [3 4]
  4           5          12            [5 ................... 12]
  5           6          11              [6 ............ 11]
  2           7           8                [7 8]
  6           9          10                    [9 10]

Finish times are valuable. In a DAG, ordering vertices by decreasing finish time gives a topological order, and finish times drive Kosaraju's algorithm for strongly connected components.

Python Discovery and finish times

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.

Finding a path (not necessarily shortest)

DFS can answer "is target reachable from start?" and give a path. Unlike BFS, the path it finds is not guaranteed to be shortest. Keep the current path in a list, add a vertex when you enter it and remove it when you back out (backtracking style).

Python DFS path versus BFS path

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.

DFS found the four-edge path 0, 1, 4, 5, 6 because it tried vertex 1 first; BFS found the three-edge path 0, 2, 5, 6. When you need the fewest edges, use BFS.

Applications

Many problems are "DFS plus a small twist":

  • Reachability and connected components: run DFS from every unvisited vertex; each run discovers one component (components and flood fill).
  • Cycle detection: in an undirected graph, reaching a visited vertex that is not your parent means a cycle; in a directed graph, reaching a vertex that is still open means a cycle (cycle detection).
  • Topological sorting: reverse finish order of a DAG (topological sort).
  • Bridges and articulation points: use discovery times and low-links (bridges).
  • Solving puzzles and mazes, generating all paths: DFS with backtracking.
Python Counting components 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.

When you only need which vertices are reachable, not a specific visiting order, you can mark on push in the iterative version, as above. If you need the true DFS order (discovery times), mark when you pop or use recursion.

Recursion depth

Each recursive call uses stack space, so the space of DFS is O(V) in the worst case (a single long path). Python stops at a recursion limit of about 1,000. The iterative version has no such limit.

Python Recursion limit on a long chain (fails on purpose)

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.

The recursive version fails on purpose here (the error is caught and reported). The iterative one handles 5,000 vertices without trouble. Raising sys.setrecursionlimit is possible but risky, since a very deep recursion can crash the interpreter. Prefer the explicit stack for large inputs.

Complexity

With an adjacency list, DFS takes O(V + E) time: each vertex is visited once and each edge is examined once from each end. Space is O(V) for the visited set plus the stack or call stack (up to V deep). With an adjacency matrix the time becomes O(Vยฒ).

DFS versus BFS

DFS BFS
Data structure stack (or recursion) queue
Order goes deep first closest first
Shortest path (unweighted) no yes
Memory on wide graphs small can hold a whole level
Memory on deep graphs up to V deep small
Typical uses cycles, components, topological order, backtracking shortest paths, levels, spreading

Common mistakes

  • No visited set, which loops forever on any graph with a cycle (including every undirected edge, since a neighbor's neighbor is you).
  • Relying on recursion for large graphs. Switch to an explicit stack.
  • Expecting DFS to find shortest paths. It finds a path.
  • Using a shared default list or set as a visited argument (def dfs(u, visited=set())); the default is created once and shared across calls. Create visited inside or pass it explicitly.
  • Marking visited at the wrong time in the iterative version, which changes the visiting order. Mark on pop to reproduce true DFS order.
  • Forgetting disconnected graphs. Loop over all vertices if you need to cover everything.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. Which structure does depth-first search use, explicitly or through recursion?

    DFS keeps the path of open vertices on a stack; the call stack plays that role in the recursive version.
  2. 2. What is the time complexity of DFS on a graph stored as an adjacency list?

    Each vertex is visited once and each edge is scanned a constant number of times.
  3. 3. Why can the recursive DFS crash on a very long chain of vertices?

    A path of n vertices needs n nested calls, which exceeds Python's recursion limit for large n.
  4. 4. Does DFS from a start vertex always find the shortest path to a target in an unweighted graph?

    DFS dives deep along one route first. Use BFS for fewest edges.
  5. 5. For a DAG, what does ordering vertices by decreasing DFS finish time give?

    A vertex finishes only after everything it points to has finished, so reversing finish times puts dependencies first.

Summary

  • DFS follows one branch as deep as possible, then backtracks; it uses a stack (or recursion) and a visited set.
  • Time is O(V + E), space O(V).
  • The recursive version is short but limited by Python's recursion depth; the iterative version with an explicit stack has no such limit, and pushing neighbors in reverse reproduces the recursive order.
  • Discovery and finish times nest like parentheses; finish order powers topological sorting and strongly connected components.
  • DFS finds a path, not the shortest one; use BFS for fewest edges.
  • Typical uses are components, cycle detection, topological order, bridges and backtracking.

Next: Connected Components and Flood Fill