Implementation of DFS

In this lesson, we’ll solve the problem of detecting cycles in directed graphs by implementing DFS.

Implementation notes

The easiest way to implement DFS is as a recursive procedure:

1. Mark the current node as “in progress.”
2. Recursively process all nodes behind discovery edges.
3. Mark the current node as done.

Due to the recursion occuring between starting and finishing a node, we automatically explore deeper nodes first before going up to shallower nodes again.

So, in principle, our depth-first search procedure should be a recursive function

void dfs(int u) {}

that performs DFS from the starting node u.

As we mostly need to perform operations on all neighboring edges of a node, we’ll make use of the adjacency list graph representation. We are considering unweighted graphs here, but the implementation for weighted graphs is very similar. We’ll simply ignore the values of the weights.

But now our DFS procedure additionally needs to access some “global” state such as:

• the adjacency list of the graph.
• the current state or color of each node.

One option would be to pass this state to the dfs routine additionally, like in

void dfs(int u, vector<vector<int>> const &adjacencyList, vector<NodeState> &state) {}

However, this is unwieldy, especially when we want to keep track of more state during the search, such as node predecessors or distances.

Instead, we’ll implement our cycle detection algorithm as a class where this state is stored in the member variables.

Avoiding stack overflows

There is one downside of implementing DFS recursively. As each recursive function call creates a stack frame, it is possible to run into stack overflows on very large graphs.