Depth-first traversal

Lesson · 10 min read · Graphs · Traversing a graph

Follow one branch to its end before trying the next: the recursive search behind cycle detection, components and topological order.

One branch at a time

An array is traversed with a loop because its items sit in a line. A graph has no line: from any node there may be several ways on, and some lead back to nodes already seen. A traversal needs a rule for which way to go next and a record of where it has been.

Depth-first search takes the simplest rule. From the current node, step to a neighbour that has not been visited and carry on from there. Only when a node has no unvisited neighbour left does the search back up to the node it came from and try that node's next neighbour.

From 0 the search goes down to 1 and 3, backs up to 1, then goes to 4. The whole left branch is finished before 2 is touched.

On a tree this is exactly preorder traversal. On a graph the one addition is the visited set, because a cycle would otherwise send the search round for ever.

The algorithm

The rule is naturally recursive: searching from u means marking u and then searching from each of its unvisited neighbours in turn. The call stack remembers the way back.

Depth-first traversal

dfs(u)

Add u to visited (and do whatever the problem needs with it).
For each neighbour v of u: if v is not in visited, call dfs(v).

traverse(graph)

Create an empty visited set.
For each node s of the graph: if s is not in visited, call dfs(s).

The outer loop matters. One call to dfs reaches only the nodes connected to where it started; if the graph is in several pieces, the rest stay unvisited.

outer loop→

Left: dfs(0) reaches 0 to 4 and stops. Right: the outer loop finds 5 unvisited and calls dfs(5).

Step by step

Here is the traversal on that graph, with neighbours tried in increasing order. Watch the call stack: it grows as the search goes deeper and shrinks as it backtracks, and its contents are always the path from the start to the current node.

Depth-first traversal from node 0. The call stack is shown bottom to top.

Step 1 / 15

call stack (bottom → top)
00
visit order
00
Start a new search at 0: mark it visited and push it on the call stack.
Step 2 / 15

call stack (bottom → top)
0011
visit order
0011
From 0, go to its first unvisited neighbour, 1. Mark it and push it.
Step 3 / 15

call stack (bottom → top)
001132
visit order
001132
From 1, go to its first unvisited neighbour, 3. Mark it and push it.
Step 4 / 15

call stack (bottom → top)
00113223
visit order
00113223
From 3, go to its first unvisited neighbour, 2. Mark it and push it.
Step 5 / 15

call stack (bottom → top)
001132
visit order
00113223
Every neighbour of 2 is visited: 2 is finished and popped, so the search backtracks to 3.
Step 6 / 15

call stack (bottom → top)
00113243
visit order
0011322344
From 3, go to its first unvisited neighbour, 4. Mark it and push it.
Step 7 / 15

call stack (bottom → top)
001132
visit order
0011322344
Every neighbour of 4 is visited: 4 is finished and popped, so the search backtracks to 3.
Step 8 / 15

call stack (bottom → top)
0011
visit order
0011322344
Every neighbour of 3 is visited: 3 is finished and popped, so the search backtracks to 1.
Step 9 / 15

call stack (bottom → top)
00
visit order
0011322344
Every neighbour of 1 is visited: 1 is finished and popped, so the search backtracks to 0.
Step 10 / 15

call stack (bottom → top)
empty0
visit order
0011322344
Every neighbour of 0 is visited: 0 is finished and popped.
Step 11 / 15

call stack (bottom → top)
empty0
visit order
0011322344
The search from the previous start is exhausted but 5 is unvisited: this graph is not connected, so the outer loop starts again at 5.
Step 12 / 15

call stack (bottom → top)
50
visit order
001132234455
Start a new search at 5: mark it visited and push it on the call stack.
Step 13 / 15

call stack (bottom → top)
5061
visit order
00113223445566
From 5, go to its first unvisited neighbour, 6. Mark it and push it.
Step 14 / 15

call stack (bottom → top)
50
visit order
00113223445566
Every neighbour of 6 is visited: 6 is finished and popped, so the search backtracks to 5.
Step 15 / 15

call stack (bottom → top)
empty0
visit order
00113223445566
Every neighbour of 5 is visited: 5 is finished and popped. Every node is visited. Order: 0, 1, 3, 2, 4, 5, 6.

current nodeon the call stackfinishededge the search followed

Implementation

The graph is an adjacency list. The recursive function needs the list and the visited set; in the languages below they are captured from the enclosing function or passed by reference, so every call shares one copy. The order of visits is recorded so the result can be checked.

def dfs_order(n, edges):
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)            # undirected: store both directions
    for nb in adj:
        nb.sort()                   # smallest neighbour first
    seen = [False] * n
    order = []

    def dfs(u):
        seen[u] = True              # mark on entry
        order.append(u)
        for v in adj[u]:
            if not seen[v]:
                dfs(v)

    for s in range(n):              # one search per unvisited part
        if not seen[s]:
            dfs(s)
    return order

#include <algorithm>
#include <functional>
#include <vector>

std::vector<int> solve(int n, const std::vector<std::vector<int>>& edges) {
    std::vector<std::vector<int>> adj(n);
    for (const auto& e : edges) {
        adj[e[0]].push_back(e[1]);
        adj[e[1]].push_back(e[0]);          // undirected: store both directions
    }
    for (auto& nb : adj) std::sort(nb.begin(), nb.end());
    std::vector<bool> seen(n, false);
    std::vector<int> order;
    std::function<void(int)> dfs = [&](int u) {
        seen[u] = true;                     // mark on entry
        order.push_back(u);
        for (int v : adj[u]) if (!seen[v]) dfs(v);
    };
    for (int s = 0; s < n; ++s) if (!seen[s]) dfs(s);
    return order;
}

import java.util.*;

class Solution {
    private List<List<Integer>> adj;
    private boolean[] seen;
    private int[] order;
    private int count;

    public int[] dfsOrder(int n, int[][] edges) {
        adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) {
            adj.get(e[0]).add(e[1]);
            adj.get(e[1]).add(e[0]);            // undirected: store both directions
        }
        for (List<Integer> nb : adj) Collections.sort(nb);
        seen = new boolean[n];
        order = new int[n];
        count = 0;
        for (int s = 0; s < n; s++) if (!seen[s]) dfs(s);
        return order;
    }

    private void dfs(int u) {
        seen[u] = true;                         // mark on entry
        order[count++] = u;
        for (int v : adj.get(u)) if (!seen[v]) dfs(v);
    }
}

function dfsOrder(n, edges) {
  const adj = Array.from({ length: n }, () => []);
  for (const [u, v] of edges) {
    adj[u].push(v);
    adj[v].push(u);                // undirected: store both directions
  }
  for (const nb of adj) nb.sort((a, b) => a - b);
  const seen = new Array(n).fill(false);
  const order = [];
  const dfs = u => {
    seen[u] = true;                // mark on entry
    order.push(u);
    for (const v of adj[u]) if (!seen[v]) dfs(v);
  };
  for (let s = 0; s < n; s++) if (!seen[s]) dfs(s);
  return order;
}

fn solve(n: i64, edges: &[[i64; 2]]) -> Vec<i64> {
    let n = n as usize;
    let mut adj = vec![Vec::new(); n];
    for e in edges {
        let (u, v) = (e[0] as usize, e[1] as usize);
        adj[u].push(v);
        adj[v].push(u);                         // undirected: store both directions
    }
    for nb in adj.iter_mut() {
        nb.sort();
    }
    fn dfs(u: usize, adj: &[Vec<usize>], seen: &mut Vec<bool>, order: &mut Vec<i64>) {
        seen[u] = true;                         // mark on entry
        order.push(u as i64);
        for &v in &adj[u] {
            if !seen[v] {
                dfs(v, adj, seen, order);
            }
        }
    }
    let mut seen = vec![false; n];
    let mut order = Vec::with_capacity(n);
    for s in 0..n {
        if !seen[s] {
            dfs(s, &adj, &mut seen, &mut order);
        }
    }
    order
}

import Data.List (foldl', sort)
import qualified Data.Map.Strict as M
import qualified Data.Set as S

solve :: Int -> [[Int]] -> [Int]
solve n edges = reverse (snd (foldl' start (S.empty, []) [0 .. n - 1]))
  where
    adj = M.map sort (M.fromListWith (++) (concat [[(u, [v]), (v, [u])] | [u, v] <- edges]))
    -- the state is (visited set, visit order reversed)
    start acc@(seen, _) s
      | S.member s seen = acc
      | otherwise = dfs acc s
    dfs (seen, order) u = foldl' visit (S.insert u seen, u : order) (M.findWithDefault [] u adj)
    visit acc@(seen, _) v
      | S.member v seen = acc
      | otherwise = dfs acc v

The same code is the reference solution to Depth-first order of a graph, where it is compiled and run against the tests in all six languages.

Without recursion, an explicit stack does the same job. To visit nodes in the same order as the recursive version, the stack must remember how far through each node's neighbours the search has got:

def dfs_iterative(adj, s, visited):
    visited.add(s)
    stack = [(s, 0)]                     # (node, index of the next neighbour to try)
    while stack:
        u, i = stack[-1]
        if i == len(adj[u]):
            stack.pop()                  # every neighbour tried: backtrack
            continue
        stack[-1] = (u, i + 1)
        v = adj[u][i]
        if v not in visited:
            visited.add(v)
            stack.append((v, 0))

void dfs_iterative(const std::vector<std::vector<int>>& adj, int s, std::vector<bool>& visited) {
    visited[s] = true;
    std::vector<std::pair<int, size_t>> stack = {{s, 0}};   // (node, index of the next neighbour to try)
    while (!stack.empty()) {
        auto& [u, i] = stack.back();
        if (i == adj[u].size()) { stack.pop_back(); continue; }   // every neighbour tried: backtrack
        int v = adj[u][i++];
        if (!visited[v]) {
            visited[v] = true;
            stack.push_back({v, 0});
        }
    }
}

static void dfsIterative(List<List<Integer>> adj, int s, boolean[] visited) {
    visited[s] = true;
    Deque<int[]> stack = new ArrayDeque<>();
    stack.push(new int[] {s, 0});                    // {node, index of the next neighbour to try}
    while (!stack.isEmpty()) {
        int[] top = stack.peek();
        int u = top[0];
        if (top[1] == adj.get(u).size()) { stack.pop(); continue; }   // every neighbour tried: backtrack
        int v = adj.get(u).get(top[1]++);
        if (!visited[v]) {
            visited[v] = true;
            stack.push(new int[] {v, 0});
        }
    }
}

function dfsIterative(adj, s, visited) {
    visited.add(s);
    const stack = [[s, 0]];                          // [node, index of the next neighbour to try]
    while (stack.length) {
        const top = stack[stack.length - 1];
        const u = top[0];
        if (top[1] === adj[u].length) { stack.pop(); continue; }   // every neighbour tried: backtrack
        const v = adj[u][top[1]++];
        if (!visited.has(v)) {
            visited.add(v);
            stack.push([v, 0]);
        }
    }
}

fn dfs_iterative(adj: &[Vec<usize>], s: usize, visited: &mut [bool]) {
    visited[s] = true;
    let mut stack = vec![(s, 0usize)];               // (node, index of the next neighbour to try)
    while let Some(top) = stack.last_mut() {
        let (u, i) = *top;
        if i == adj[u].len() { stack.pop(); continue; }   // every neighbour tried: backtrack
        top.1 += 1;
        let v = adj[u][i];
        if !visited[v] {
            visited[v] = true;
            stack.push((v, 0));
        }
    }
}

dfsIterative :: Array Int [Int] -> Int -> Set.Set Int
dfsIterative adj s = go (Set.singleton s) [(s, adj ! s)]
  where
    -- each stack entry is a node and the neighbours it has not tried yet
    go seen [] = seen
    go seen ((_, []) : rest) = go seen rest                       -- every neighbour tried: backtrack
    go seen ((u, v : vs) : rest)
      | Set.member v seen = go seen ((u, vs) : rest)
      | otherwise = go (Set.insert v seen) ((v, adj ! v) : (u, vs) : rest)

The common shortcut, popping a node and pushing all its neighbours at once, also visits every node, but in a different order. That is fine for counting components and wrong for anything that depends on the recursive order, such as finishing times.

Complexity

Each node is entered once, because it is marked before its neighbours are explored. Each edge is looked at twice in an undirected graph (once from each end) and once in a directed one. Building the adjacency list is O(n + m) as well.

TimeO(n + m)

SpaceO(n)

The visited set holds up to n nodes. The call stack is as deep as the longest path the search follows: 1 for a star, n for a path. A path of 10⁵ nodes overflows the default stack in Python (limit 1,000 frames), and can overflow it in C++ and Java; use the iterative form for inputs that large.