Depth-first search

Depth-first search (DFS) finds every vertex of a graph that can be reached from a start vertex. Run it from every vertex not yet reached, and it splits a graph or a grid into connected components. If you need the fewest edges to each vertex, use breadth-first search instead.

Explanation

For example, a small cave has 6 rooms joined by corridors. Which rooms can you reach from room 1? Explore it the way you would solve a maze: keep taking the first corridor you haven't tried until you reach a dead end, then walk back to the last room that still has a corridor you haven't tried, and take that one.

Fig. 1. A corridor turns blue when it is walked. A solid arrow goes deeper, a dashed arrow walks back to the last room with a corridor left to try.

The walk enters every room once and ends back in room 1, when no corridor is left to try. But real caves are rarely this simple. Can you get from room 1 to room 7 in this one, exploring it the same way?

Fig. 2. Can you get from room 1 to room 7? Room 8 has no corridors.

This cave has a loop (a cycle) through rooms 1, 2, 4 and 3, so you need to keep track of the rooms you have been in. Otherwise you go round the loop forever.

Depth-first search (DFS) marks each room when it first enters it, keeps following the first corridor that leads to an unmarked room, and walks back when there is none.

Room 1 is marked. The current route, in the boxes below the cave, is just room 1.

Room 2 is not marked yet, so the search goes deeper from room 1 to room 2 and marks it.

Room 1 is already marked, so the search doesn't take the corridor from room 2 to room 1.

Room 4 is not marked yet, so the search goes deeper from room 2 to room 4 and marks it.

Room 2 is already marked, so the search doesn't take the corridor from room 4 to room 2.

Room 3 is not marked yet, so the search goes deeper from room 4 to room 3 and marks it.

Room 1 is already marked, so the search doesn't take the corridor from room 3 to room 1.

Room 4 is already marked, so the search doesn't take the corridor from room 3 to room 4.

Room 6 is not marked yet, so the search goes deeper from room 3 to room 6 and marks it.

Room 3 is already marked, so the search doesn't take the corridor from room 6 to room 3.

Room 7 is not marked yet, so the search goes deeper from room 6 to room 7 and marks it.

Room 6 is already marked, so the search doesn't take the corridor from room 7 to room 6.

Room 7 has no corridor left to an unmarked room, so the search walks back to room 6.

Room 6 has no corridor left to an unmarked room, so the search walks back to room 3.

Room 3 has no corridor left to an unmarked room, so the search walks back to room 4.

Room 5 is not marked yet, so the search goes deeper from room 4 to room 5 and marks it.

Room 2 is already marked, so the search doesn't take the corridor from room 5 to room 2.

Room 4 is already marked, so the search doesn't take the corridor from room 5 to room 4.

Room 5 has no corridor left to an unmarked room, so the search walks back to room 4.

Room 4 has no corridor left to an unmarked room, so the search walks back to room 2.

Room 5 is already marked, so the search doesn't take the corridor from room 2 to room 5.

Room 2 has no corridor left to an unmarked room, so the search walks back to room 1.

Room 3 is already marked, so the search doesn't take the corridor from room 1 to room 3.

Room 1 has no corridor left to try, so the search ends. Rooms 1 to 7 are marked, and room 8 is never reached.

1/24

Fig. 3. Step through DFS with the buttons. Rooms on the current route are light blue, and the current route is shown in the boxes below the cave. A room turns green when the search walks back from it. A solid arrow goes deeper, a grey arrow points to a room that is already marked, and a dashed arrow walks back.

The search reached rooms 1 to 7, in the order 1, 2, 4, 3, 6, 7, 5. Room 8 has no corridors, so it is never reached.

Connected components

Some caves are made of separate parts with no corridor between them; room 8 in Fig. 2 is a part on its own. Each part is a connected component. To find them all, start a new search from every room that isn't marked yet: each search marks one whole part.

No room is coloured yet.

Room 1 is the first room that isn't coloured yet, so a new search starts there and colours it blue.

The search goes from room 1 to room 2 and colours it blue too.

The search goes from room 2 to room 4 and colours it blue too.

The search goes from room 1 to room 3 and colours it blue too.

Room 5 is the first room that isn't coloured yet, so a new search starts there and colours it green.

The search goes from room 5 to room 6 and colours it green too.

The search goes from room 6 to room 7 and colours it green too.

Room 8 is the first room that isn't coloured yet, so a new search starts there and colours it amber.

The search goes from room 8 to room 9 and colours it amber too.

Every room is coloured after 3 searches, so the cave has 3 connected components.

1/11

Fig. 4. Each search colours one connected component. The next search starts at the first room that isn't coloured yet.

Grids

On a grid, the components are the open areas of a floor plan with walls. Each open cell is like a room, and you can move between cells that share a side. This floor plan has 4 areas.

Fig. 5. Each search fills one area. The next search starts at the first open cell that isn't marked yet.

Implementation

The rooms are the vertices of a graph, and the corridors are its edges. In code and in the proof we say vertex and edge; the cave examples keep rooms and corridors. The start vertex is s. The graph is stored as an adjacency list, where adj[v] lists the neighbours of v.

The marks are kept in an array marked. The walk is a recursive function dfs(v): going deeper is a call, and walking back is a return. The calls that have started and not yet returned are the current route, which the program keeps in its call stack.

For a start vertex s, the algorithm is:

1. Initialise: no vertex is marked; call dfs(s).

2. Mark it: dfs(v) sets marked[v] = true.

3. Expand its edges: for each neighbour u of v that is not marked, go deeper with dfs(u).

4. Walk back: when all edges of v are checked, dfs(v) returns to the vertex v was reached from.

5. Stop when dfs(s) returns.

In Fig. 3, the walk back from room 7 to 6 to 3 to 4 is the returns of dfs(7), dfs(6) and dfs(3).

The program reads n and m, then m lines u v: a two-way edge between u and v. Vertices are numbered from 1 to n, and the start is vertex 1. The program prints the vertices in the order they are reached. Then it prints the route the search found from vertex 1 to a target t, using parent[u]: the vertex whose call went deeper to u. Walking back along parent from t ends at vertex 1, where parent[1] = 0. For the cave in Fig. 2 the input is:

8 8
1 2
1 3
2 4
2 5
3 4
3 6
4 5
6 7

The comments name the steps above.

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

vector<vector<int>> adj;
vector<bool> marked;
vector<int> order;
vector<int> parent;   // only needed to print the route

void dfs(int v) {
    // mark it
    marked[v] = true;
    order.push_back(v);

    // expand its edges
    for (int u : adj[v]) {
        if (!marked[u]) {
            parent[u] = v;   // only needed to print the route
            dfs(u);  // go deeper
        }
    }
    // walk back: return to the vertex v was reached from
}

int main() {
    int n, m;
    cin >> n >> m;
    adj.resize(n + 1);
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);   // remove this line if the graph is directed
    }

    // initialise
    marked.assign(n + 1, false);
    parent.assign(n + 1, 0);   // only needed to print the route
    dfs(1);
    // stop: dfs(1) has returned

    for (int i = 0; i < (int)order.size(); i++) {
        cout << order[i] << (i + 1 < (int)order.size() ? ' ' : '\n');
    }

    // print the route found from 1 to t; remove this block if you only need which vertices are reached
    int t = 7;
    if (marked[t]) {
        vector<int> route;
        for (int v = t; v != 0; v = parent[v]) route.push_back(v);
        reverse(route.begin(), route.end());
        for (int v : route) cout << v << ' ';
        cout << '\n';
    }
}

For the cave in Fig. 2 the program prints 1 2 4 3 6 7 5 and then the route 1 2 4 3 6 7. In a directed graph DFS finds the vertices that can be reached along the arrows.

Each vertex is marked at most once, and each edge is checked twice in an undirected graph, once from each end, and once in a directed graph. So DFS takes O(n + m) time and O(n + m) memory for adj, marked and the current route, which can hold up to n calls.

Counting components

In code, an outer loop goes through all vertices and starts a new search from each one that is not marked yet. Each search marks exactly one component:

// initialise
marked.assign(n + 1, false);
int count = 0;
for (int v = 1; v <= n; v++) {
    if (!marked[v]) {
        count++;   // a new component starts at v
        dfs(v);
    }
}
cout << count << '\n';

The time is still O(n + m), because each vertex is marked once over all the searches.

This needs two-way edges. With a single one-way edge from vertex 2 to vertex 1, the loop counts 2 components: the search from vertex 1 reaches nothing else, and vertex 2 starts its own search. With the edge from 1 to 2 it counts 1.

Fill a grid

In code, the floor plan from Fig. 5 is a 5 \times 5 grid. Each open cell is a vertex, and two open side neighbours are joined by an edge. We write (r, c) for the cell in row r and column c, numbered from 0 as in the code. The outer loop goes through the cells row by row and starts a new search from each open cell that is not marked yet. Each search fills one area. Filling an area like this is called a flood fill.

The program reads R and C, the number of rows and columns, and then the R rows of the plan as strings into g, with # for a wall and . for an open cell. area[r][c] is 0 for a cell that is not marked yet, and otherwise the number of its area, so it works as the mark. The four moves are listed in dr and dc. Before reading a cell, check that it is inside the grid and is not a wall:

int R, C;
vector<string> g;
vector<vector<int>> area;

int dr[] = {-1, 1, 0, 0};   // up, down, left, right
int dc[] = {0, 0, -1, 1};

void dfs(int r, int c, int id) {
    // mark it
    area[r][c] = id;
    // expand its edges
    for (int k = 0; k < 4; k++) {
        int nr = r + dr[k], nc = c + dc[k];
        if (nr < 0 || nr >= R || nc < 0 || nc >= C) continue;  // outside the grid
        if (g[nr][nc] == '#') continue;                        // wall
        if (area[nr][nc] == 0) dfs(nr, nc, id);
    }
}

// in main: read the plan, initialise, then one search per area
cin >> R >> C;
g.resize(R);
for (string& row : g) cin >> row;
area.assign(R, vector<int>(C, 0));
int areas = 0;
for (int r = 0; r < R; r++)
    for (int c = 0; c < C; c++)
        if (g[r][c] != '#' && area[r][c] == 0) {
            areas++;
            dfs(r, c, areas);
        }

Each cell has at most 4 edges, so the whole fill takes O(R \cdot C) time.

Without recursion

To avoid deep recursion, keep the vertices to try next in a stack, a list where the last item added is the first one taken out. Take a vertex from the top. If it is already marked, skip it. Otherwise mark it and push its neighbours that are not marked yet. A vertex can be pushed more than once before it is taken, so the check after taking it is needed. Pushing the neighbours in reverse order makes the first neighbour come out first, which keeps the same order as the recursion.

// initialise (needs <stack>)
vector<bool> marked(n + 1, false);
stack<int> st;
st.push(1);

while (!st.empty()) {            // stop: when the stack is empty
    // take the next vertex
    int v = st.top();
    st.pop();
    if (marked[v]) continue;     // pushed twice, already marked

    // mark it
    marked[v] = true;
    order.push_back(v);

    // expand its edges, last neighbour first
    for (int i = (int)adj[v].size() - 1; i >= 0; i--) {
        int u = adj[v][i];
        if (!marked[u]) st.push(u);
    }
}

On the cave in Fig. 2 order is 1 2 4 3 6 7 5, as with the recursion. It makes 9 pushes for 7 rooms: rooms 3 and 5 are pushed twice. Each edge pushes at most one vertex from each end, so the stack holds at most 2m + 1 entries, and the time is still O(n + m).

Correctness proof

The search marks only vertices that can be reached from $s$: each vertex other than $s$ is marked by a call that came along an edge from a marked vertex. So it remains to show that every vertex that can be reached gets marked.

The invariant is that a mark is never removed, and when dfs(v) returns, every neighbour of $v$ is marked. The second part holds because dfs(v) checks every edge of $v$ before it returns. Each neighbour $u$ was either marked already, or the search called dfs(u), which marked it.

Take a vertex $t$ that can be reached from $s$, and suppose it is not marked at the end. Look along a path from $s$ to $t$. The vertex $s$ is marked and $t$ is not, so somewhere on the path a marked vertex $v$ is followed by a vertex $u$ that is not marked. But dfs(v) was called and has returned, so all neighbours of $v$, including $u$, are marked. This contradicts the choice of $u$. So every vertex that can be reached is marked.

The search also stops: each vertex is marked once, so dfs is called at most $n$ times.

Common mistakes

• Using DFS to find the fewest corridors: it keeps the first route it finds, and that route can be long. For the fewest corridors or moves, use breadth-first search.

• Remembering only the vertex the search came from, if (u != from) dfs(u, v);, instead of marking: on a graph with a cycle the calls go round it until the program crashes. That check is enough only on a tree; on any other graph, use the marked array.

• Storing a two-way edge in one list only, with adj[u].push_back(v); and no adj[v].push_back(u);, so the search can't follow it from the other end and misses vertices. Add every two-way edge to both lists.

• Removing the mark when walking back, with marked[v] = false; at the end of dfs, so the search tries every path that doesn't repeat a vertex and the number of calls grows exponentially. Keep the marks; removing them on purpose to try every path is backtracking, only for problems that need every path.

• Leaving out if (marked[v]) continue; in the stack version, so a vertex pushed twice is handled and printed twice. Keep the check right after taking a vertex.

Similar algorithms

For "can I get there" or "how many components", breadth-first search works as well, also in O(n + m). Recursive DFS is shorter to write.

A disjoint set union answers "are these two vertices in the same component?" when edges are added one by one between the questions, without running a new search each time.

Cycle detection is a DFS that looks for a marked neighbour other than the vertex it came from.

Topological sort runs DFS on a directed graph without cycles and lists the vertices in the order their calls return, reversed.

Practice