Depth First Search Algorithm Explained
DFS in C++
Recursive DFS in C++
You already know how DFS works by going as deep as possible down one path before backtracking. In C++, implementing this recursively is straightforward. We can use a std::vector of booleans to keep track of visited nodes and a std::vector<std::vector<int>> to represent our graph's adjacency list.
The core of the recursive approach is a function that marks a node as visited, processes it, and then calls itself for each unvisited neighbor.
#include <iostream>
#include <vector>
// A utility function for the recursive DFS traversal
void dfs_recursive(int u, std::vector<std::vector<int>>& adj, std::vector<bool>& visited) {
// Mark the current node as visited and print it
visited[u] = true;
std::cout << u << " ";
// Recur for all the vertices adjacent to this vertex
for (int v : adj[u]) {
if (!visited[v]) {
dfs_recursive(v, adj, visited);
}
}
}
int main() {
int V = 5; // Number of vertices
std::vector<std::vector<int>> adj(V);
// Add edges for a simple graph
adj[0].push_back(1);
adj[0].push_back(2);
adj[1].push_back(3);
adj[2].push_back(4);
std::vector<bool> visited(V, false);
std::cout << "DFS starting from vertex 0: ";
dfs_recursive(0, adj, visited);
std::cout << std::endl;
return 0;
}
In this example, dfs_recursive is the heart of the operation. It takes the current vertex u, the adjacency list adj, and the visited vector. By passing the adj and visited vectors by reference (&), we avoid making slow, memory-intensive copies with each recursive call.
Iterative DFS with a Stack
While recursion is elegant, it can lead to a stack overflow error on very deep graphs. The iterative approach avoids this by using an explicit std::stack data structure to manage the nodes to visit. This method mimics the function call stack that recursion uses behind the scenes.
The process is simple: push the starting node onto the stack. Then, in a loop, pop a node, process it if it hasn't been visited, mark it as visited, and push all its unvisited neighbors onto the stack.
#include <iostream>
#include <vector>
#include <stack>
// An iterative DFS traversal function
void dfs_iterative(int start_node, int V, std::vector<std::vector<int>>& adj) {
std::vector<bool> visited(V, false);
std::stack<int> s;
// Push the starting source node
s.push(start_node);
while (!s.empty()) {
// Pop a vertex from stack
int u = s.top();
s.pop();
// Stack may have duplicates, so we check if it's already visited
if (!visited[u]) {
std::cout << u << " ";
visited[u] = true;
}
// Get all adjacent vertices. If an adjacent has not been
// visited, push it to the stack.
for (int v : adj[u]) {
if (!visited[v]) {
s.push(v);
}
}
}
}
Note that the order of traversal can differ slightly from the recursive version depending on the order you push neighbors onto the stack, but the fundamental depth-first principle remains the same.
Handling Edge Cases
Real-world graphs aren't always simple. They can be disconnected or contain cycles. Our DFS implementation needs to handle these cases gracefully.
Disconnected Graphs
What if a graph has multiple components that are not connected to each other? A single DFS call starting from one node will only explore the component that node belongs to. To traverse the entire graph, we must loop through every vertex and start a new DFS traversal if it hasn't been visited yet.
void traverse_graph(int V, std::vector<std::vector<int>>& adj) {
std::vector<bool> visited(V, false);
// Iterate through all vertices
for (int i = 0; i < V; i++) {
// If vertex i has not been visited, start a DFS from it
if (!visited[i]) {
// You can use either dfs_recursive or an iterative version here
dfs_recursive(i, adj, visited);
}
}
}
This wrapper function ensures that even if the graph is made of several separate islands of nodes, we'll eventually visit every single one.
Cycle Detection
We can also adapt DFS to detect cycles. The logic changes slightly depending on whether the graph is directed or undirected.
For an undirected graph, we find a cycle if we encounter a visited vertex that is not the immediate parent of the current vertex in the DFS traversal. We can track the parent by passing it as an argument in our recursive function.
For a directed graph, we need to track the nodes currently in our recursion stack. If we encounter a node that's already in the stack, we've found a back edge, which indicates a cycle.
// Cycle detection in a directed graph using DFS
// Returns true if the graph contains a cycle, else false.
bool isCyclicUtil(int u, std::vector<std::vector<int>>& adj,
std::vector<bool>& visited, std::vector<bool>& recursionStack) {
visited[u] = true;
recursionStack[u] = true;
// Recur for all the vertices adjacent to this vertex
for (int v : adj[u]) {
if (!visited[v]) {
if (isCyclicUtil(v, adj, visited, recursionStack)) {
return true;
}
} else if (recursionStack[v]) {
// If v is visited and in the current recursion stack, there's a cycle
return true;
}
}
// Remove the vertex from the recursion stack before returning
recursionStack[u] = false;
return false;
}
// Main function to check for cycles
bool isCyclic(int V, std::vector<std::vector<int>>& adj) {
std::vector<bool> visited(V, false);
std::vector<bool> recursionStack(V, false);
// Call the recursive helper function to detect cycle in different DFS trees
for (int i = 0; i < V; i++) {
if (!visited[i]) {
if (isCyclicUtil(i, adj, visited, recursionStack)) {
return true;
}
}
}
return false;
}
Here, recursionStack keeps track of the vertices in the current traversal path. If we find a neighbor v that is already in recursionStack, we have a back edge from u to v, and thus a cycle.
When implementing a recursive Depth-First Search (DFS) in C++, why is it generally better to pass the adjacency list and visited vectors by reference (&) to the recursive function?
What is the primary advantage of an iterative DFS implementation using an explicit std::stack over a recursive one?
With these C++ patterns for recursion, iteration, and edge cases, you have a robust toolkit for applying DFS to a variety of graph problems.