How to implement DFS in C++

Key takeaways:
Depth-first search (DFS) explores as deep as possible into a graph along each branch before backtracking, making it suitable for exploration and connectivity problems.
DFS can be implemented:
Recursively (using the call stack)
Iteratively (using an explicit stack)
Common graph representations include:
Adjacency list: Space-efficient and widely used for sparse graphs.
Adjacency matrix: Simple but consumes more space, especially for large graphs.
DFS traversal order depends on the order of neighbors in the graph’s representation.
This variability can affect outcomes in applications like maze solving or graph searches.
DFS is versatile and forms the foundation for solving complex problems in AI, pathfinding, and graph analysis.

Depth-first search (DFS) is a fundamental graph traversal algorithm that explores nodes in a graph by moving as deep as possible along a branch before backtracking. DFS uses the “last in, first out” principle, often implemented via recursion or a stack. This makes it a powerful and straightforward tool for systematically visiting all vertices in a graph.

In essence, DFS helps discover paths and understand the structure of a graph or tree by following each path to its conclusion before exploring alternative routes.

DFS algorithm

Depth-first search (DFS) explores nodes in a graph by venturing as deep as possible along a branch before backtracking. It can be implemented using recursion (leveraging the call stack) or an explicit stack. Below is the step-by-step explanation of the DFS algorithm:

Initialization:
- Represent the graph using an adjacency list or adjacency matrix.
- Use a visited array (or a set) to track previously explored nodes.
Start at a node:
- Select a starting node (typically provided or chosen arbitrarily).
Mark as visited:
- Mark the current node as visited to prevent reprocessing.
Traverse adjacent nodes:
- For each adjacent (unvisited) node of the current node:
  - Recursively call DFS on the node (if using recursion).
  - Or push the node onto the stack (if using an iterative approach).
Backtrack:
- In the recursive approach, backtracking occurs naturally as the call stack unwinds.
- In the iterative approach, nodes are popped off the stack when all their neighbors have been processed.
Repeat until all nodes are visited:
- If disconnected components exist, restart DFS from an unvisited node until all nodes are covered.

Pseudocode for depth-first search

Here is the pseudocode for the depth-first search (DFS) algorithm, presented in both iterative and recursive forms:

Recursive approach:

function DFSIterative(start, graph):
    visited = array of false values of size graph.size     // Initialize visited array
    stack = empty stack                                   // Create an empty stack
    stack.push(start)                                     // Push the starting node
    print("DFS Iterative Traversal:")
    while stack is not empty:
        node = stack.top()
        stack.pop()
        if not visited[node]:
            visited[node] = true                         // Mark the node as visited
            print(node)                                  // Print the visited node (optional step)
            // Push all unvisited neighbors onto the stack
            for each neighbor in graph[node]:
                if not visited[neighbor]:
                    stack.push(neighbor)
    end while
end function

#include <iostream>
#include <vector>
using namespace std;
// Recursive DFS function
void DfsRecursive(int node, const vector<vector<int>>& graph, vector<bool>& visited) {
    visited[node] = true;  // Mark the current node as visited
    cout << node << " ";   // Print the visited node
    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            DfsRecursive(neighbor, graph, visited);  // Recursive call for unvisited neighbors
        }
    }
}
int main() {
    // Example graph represented as an adjacency list
    vector<vector<int>> graph = {
        {},           // Node 0 (not used)
        {2, 3},       // Node 1 connects to nodes 2, 3
        {1, 4},       // Node 2 connects to nodes 1, 4
        {1, 4},       // Node 3 connects to nodes 1, 4
        {2, 3}        // Node 4 connects to nodes 2, 3
    };
    cout << "DFS Recursive Traversal: ";
    vector<bool> visited(graph.size(), false);
    DfsRecursive(1, graph, visited);  // Start DFS from node 1
    cout << endl;
    return 0;
}

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
// Iterative DFS function
void DfsIterative(int start, const vector<vector<int>>& graph) {
    vector<bool> visited(graph.size(), false);  // Initialize visited array
    stack<int> stk;  // Create a stack for DFS
    stk.push(start);  // Push the starting node
    while (!stk.empty()) {
        int node = stk.top();
        stk.pop();
        if (!visited[node]) {
            visited[node] = true;  // Mark the node as visited
            cout << node << " ";   // Print the visited node
            // Push all unvisited neighbors onto the stack
            for (int neighbor : graph[node]) {
                if (!visited[neighbor]) {
                    stk.push(neighbor);
                }
            }
        }
    }
}
int main() {
    // Example graph represented as an adjacency list
    vector<vector<int>> graph = {
        {},           // Node 0 (not used)
        {2, 3},       // Node 1 connects to nodes 2, 3
        {1, 4},       // Node 2 connects to nodes 1, 4
        {1, 4},       // Node 3 connects to nodes 1, 4
        {2, 3}        // Node 4 connects to nodes 2, 3
    };
    cout << "DFS Iterative Traversal: ";
    DfsIterative(1, graph);  // Start DFS from node 1
    cout << endl;
    return 0;
}

Explanation of the output:

Starting from node 1:
- Uses a stack to simulate recursion.
- Pushes neighbors of the current node onto the stack in reverse order (to mimic the recursive approach’s behavior).
- Visits nodes in the order determined by the stack (Last in, first out behavior).

This program demonstrates how DFS explores the graph, making it suitable for applications such as connected component detection, cycle detection, and more.

Complexity analysis

Recursive DFS:

Time Complexity: $O(V + E)$ , where $V$ is the number of vertices and $E$ is the number of edges (each vertex and edge is visited once).
Space Complexity: $O(V)$ due to the recursion stack in the worst case (the depth of the recursion is equal to the graph’s depth).

Iterative DFS:

Time Complexity: $O(V + E)$ , as each vertex and edge is visited once.
Space Complexity: $O(V)$ due to the explicit stack used to store vertices during traversal.

Comparison of adjacency lists and adjacency matrices in the context of DFS

Here’s a detailed comparison with a focus on how they affect the performance of depth-first search (DFS):

Aspect	Adjacency List	Adjacency Matrices
Structure	List of neighbors for each vertex	V×V matrix where cell (i, j) represents an edge
Space Complexity	O(V+E), efficient for sparse graphs	O(V^2), inefficient for sparse graphs
Neighbour Lookup	Only iterates through connected neighbors	Scans the entire row for connected neighbors
DFS Performance	O(V+E), efficient for sparse graphs	O(V^2) for sparse graphs; more competitive for dense graphs
Advantages	Space-efficient for sparse graphs Fast neighbor lookup for existing edges	Constant-time edge lookup Simple for dense graphs
Disadvantages	Can consume more memory in dense graphs	Wastes space for sparse graphs Slower neighbor lookup in sparse graphs
Best Use Case	Sparse graphs with fewer edges	Dense graphs with many edges

Frequently asked questions

Haven’t found what you were looking for? Contact Us

What is a depth-first search?

Depth-first search (DFS) is a graph traversal algorithm that explores as deep as possible along a branch before backtracking. It uses recursion or a stack to systematically visit all nodes of a graph or tree.

What is DFS vs BFS?

DFS and BFS are graph traversal algorithms:

DFS (Depth-first search): Explores as deep as possible along each path before backtracking, using a stack or recursion.
BFS (Breadth-first search): Explores all neighbour at the current depth before moving to the next level, using a queue.

For more a more in-depth comparison, have a look at DFS vs. BFS

What is a DFS used for?

DFS is used in real-life scenarios such as:

Solving mazes and puzzles.
Detecting cycles in graphs.
Finding connected components in networks.
Analyzing dependencies in project management (e.g., topological sorting).

Is BFS or DFS faster?

Neither BFS nor DFS is inherently faster; their speed depends on the problem and graph structure:

BFS is more suitable for finding the shortest path in unweighted graphs.
DFS is better for exploring all paths or solving depth-based problems like puzzles. Both have a time complexity of 𝑂(𝑉+𝐸).

How to implement DFS in C++

DFS algorithm

Pseudocode for depth-first search

Recursive approach:

Iterative approach (Using a stack):

Example

Implementation

Complexity analysis

Comparison of adjacency lists and adjacency matrices in the context of DFS

Aspect

Adjacency List

Adjacency Matrices

Conclusion

Resources to prepare

Frequently asked questions

What is a depth-first search?

What is DFS vs BFS?

What is a DFS used for?

Is BFS or DFS faster?