Depth-first search

Right now, we figured out how to check whether a path from a node $a$ to another node $b$ exists. However, even though we only care about one specific destination node ($b$), the worst-case complexity of the code we wrote previously is $\mathcal{O}(n + m)$. For example, consider the following graph:

If $a=1$ and $b=8$, we traverse all nodes and all edges before realising that there is a path from $1$ to $8$.

For this reason, we usually solve this problem in two steps:

• Visit every node we can (without stopping!) from node $a$, while continuing to track visited nodes
• Then check if $b$ was visited—that is—whether or not vis[b] is true

This has the same worst-case time complexity, but we now know whether or not a path exists from $a$ to every other node in the graph.

Here’s how we’d code this:

vector<bool> vis;

void explore(int u) {
  if (vis[u]) {
    return;
  }
  vis[u] = true;
  
  for (int &i : adj[u]) {
    explore(i);
  }
}

dfs(a);
// now check the value of vis[b]!

As you may have guessed, the explore() function we just coded is commonly known as ‘depth-first search’. This is because the recursive structure of the function causes the graph to be explored ‘depth-first’.