Depth First Search

Depth First Search is one of the main graph algorithms.

Depth First Search finds the lexicographically first path in the graph from a source vertex $u$ to each vertex.

The algorithm works in $O(m + n)$ time where $n$ is the number of vertices and $m$ is the number of edges.

Applications of Depth First Search

Implementation

vector<vector<int>> g; // graph represented as an adjacency list
int n; // number of vertices

vector<int> color; // vertex color (0, 1, or 2)

vector<int> time_in, time_out; // entry and exit "times" for each vertex
int dfs_timer = 0; // "timer" to determine the current time

void dfs(int v) {
    time_in[v] = dfs_timer++;
    color[v] = 1;
    for (vector <int>::iterator i = g[v].begin(); i != g[v].end(); ++i)
        if (color[*i] == 0)
            dfs(*i);
    color[v] = 2;
    time_out[v] = dfs_timer++;
}

This is the most generic implementation of Depth First Search. In many cases entry and exit times and vertex colors are not important, so they can be discarded. In this case it will be necessary to store a boolean array $used[]$ to keep track of visited vertices. Here is the simplest implementation of DFS:

vector<vector<int>> g; // graph represented as an adjacency list
int n; // number of vertices

vector<bool> used;

void dfs(int v) {
    used[v] = true;
    for (vector<int>::iterator i = g[v].begin(); i != g[v].end(); ++i)
        if (!used[*i])
            dfs(*i);
}

Practice Problems