Implementation of DFS Algorithm in C++

Depth First Search (DFS) is a powerful tool for exploring graphs, and understanding how to implement it is key to solving many computer science problems. In this article, we’ll focus on how to write a DFS algorithm in C++.

Tip

Before diving into the implementation, it’s helpful to have a good understanding of what graphs are and the basic idea behind Depth First Search. You can learn more about them in these articles:

Representing a Graph in C++

Before we can implement DFS, we need a way to represent our graph in C++. Two common ways to do this are using an adjacency list or an adjacency matrix.

Adjacency List

An adjacency list represents the graph as a std::unordered_map where each key is a node, and its value is a std::vector of its neighboring nodes. This is efficient for sparse graphs (graphs with fewer connections).

#include <iostream>
#include <unordered_map>
#include <vector>

class Graph {
public:
    std::unordered_map<char, std::vector<char>> adjList;

    void addVertex(char vertex) {
        adjList[vertex] = std::vector<char>();
    }

    void addEdge(char source, char destination) {
        adjList[source].push_back(destination);
        // For undirected graphs, you would also add:
        // adjList[destination].push_back(source);
    }
};

In this example:

The Graph class uses an std::unordered_map called adjList to store the adjacency list.
The keys in the std::unordered_map are the vertices (nodes) of the graph, represented as char objects.
The values in the std::unordered_map are std::vector<char> objects, where each vector contains the neighbors of the corresponding vertex.
The addVertex method adds a new vertex to the graph by creating a new entry in the adjList map with an empty vector of neighbors.
The addEdge method adds an edge between two vertices by adding the destination vertex to the vector of neighbors of the source vertex. For undirected graphs, you would also add the source vertex to the list of neighbors of the destination vertex.

Adjacency Matrix

An adjacency matrix represents the graph as a 2D array where matrix[i][j] = true if there’s an edge from vertex i to vertex j, and false otherwise. It’s simpler to implement but uses more memory, especially for sparse graphs.

#include <iostream>
#include <vector>

class Graph {
public:
    std::vector<std::vector<bool>> adjMatrix;
    int numVertices;

    Graph(int numVertices) {
        this->numVertices = numVertices;
        adjMatrix.resize(numVertices, std::vector<bool>(numVertices, false));
    }

    void addEdge(int i, int j) {
        adjMatrix[i][j] = true;
        adjMatrix[j][i] = true;  // For undirected graphs
    }

    void removeEdge(int i, int j) {
        adjMatrix[i][j] = false;
        adjMatrix[j][i] = false; // For undirected graphs
    }

    bool isEdge(int i, int j) {
        return adjMatrix[i][j];
    }
};

In this example:

The Graph class uses a 2D vector of booleans called adjMatrix to represent the adjacency matrix.
The numVertices variable stores the number of vertices in the graph.
The constructor initializes the adjacency matrix with the specified number of vertices.
The addEdge method adds an edge between two vertices by setting the corresponding entry in the adjacency matrix to true. For undirected graphs, it also sets the entry in the opposite direction to true.
The removeEdge method removes an edge between two vertices by setting the corresponding entry in the adjacency matrix to false. For undirected graphs, it also sets the entry in the opposite direction to false.
The isEdge method checks if there is an edge between two vertices by returning the value of the corresponding entry in the adjacency matrix.

In this article, we will focus on representing graphs using the adjacency list, as it’s often more efficient for DFS.

Recursive DFS Implementation

The most common and intuitive way to implement DFS is using recursion. Here’s how it works:

Mark the current node as visited. We use a std::unordered_set called visited to keep track of visited nodes.
Process the current node. This could involve printing the node’s value, adding it to a list, or performing any other action.
Explore the neighbors. For each neighbor of the current node:
- If the neighbor hasn’t been visited yet, recursively call the DFS function on that neighbor.

Here’s the C++ code for the recursive DFS:

#include <iostream>
#include <unordered_map>
#include <unordered_set>
#include <vector>

class Graph {
public:
    std::unordered_map<char, std::vector<char>> adjList;

    void addVertex(char vertex) {
        adjList[vertex] = std::vector<char>();
    }

    void addEdge(char source, char destination) {
        adjList[source].push_back(destination);
        // For undirected graphs, you would also add:
        // adjList[destination].push_back(source);
    }
};

void dfsRecursive(Graph& graph, char node, std::unordered_set<char>& visited) {
    if (visited.find(node) == visited.end()) {
        visited.insert(node);
        std::cout << node << " "; // Process the node (e.g., print it)

        for (char neighbor : graph.adjList[node]) {
            dfsRecursive(graph, neighbor, visited);
        }
    }
}

int main() {
    Graph graph;
    graph.addVertex('A');
    graph.addVertex('B');
    graph.addVertex('C');
    graph.addVertex('D');
    graph.addVertex('E');
    graph.addVertex('F');

    graph.addEdge('A', 'B');
    graph.addEdge('A', 'C');
    graph.addEdge('B', 'D');
    graph.addEdge('B', 'E');
    graph.addEdge('C', 'F');
    graph.addEdge('E', 'F');

    std::cout << "DFS Traversal (Recursive): ";
    std::unordered_set<char> visited;
    dfsRecursive(graph, 'A', visited); // Start DFS from node 'A'
    std::cout << std::endl;

    return 0;
}

Here’s how you might use this function:

DFS Traversal (Recursive): A B D E F C

The function dfsRecursive takes the graph, the current node, and a visited set as input.
We check if the current node is in the visited set. If it’s not, we add it to the set and process it (in this case, print it).
Then, we iterate through the neighbors of the current node and recursively call dfsRecursive for each unvisited neighbor.

Iterative DFS Implementation using a Stack

An alternative to recursion is to use an iterative approach with a stack. This can be helpful to avoid stack overflow errors that can occur with deep recursion.

Here’s the iterative approach:

Create a stack and add the starting node to it.
Create a set to keep track of visited nodes.
While the stack is not empty:
- Pop a node from the stack.
- If the node hasn’t been visited:
  - Mark it as visited.
  - Process the node (e.g., print it).
  - Add all its unvisited neighbors to the stack.

Here’s the C++ code for the iterative DFS:

#include <iostream>
#include <stack>
#include <unordered_map>
#include <unordered_set>
#include <vector>

class Graph {
public:
    std::unordered_map<char, std::vector<char>> adjList;

    void addVertex(char vertex) {
        adjList[vertex] = std::vector<char>();
    }

    void addEdge(char source, char destination) {
        adjList[source].push_back(destination);
        // For undirected graphs, you would also add:
        // adjList[destination].push_back(source);
    }
};

void dfsIterative(Graph& graph, char startNode) {
    std::unordered_set<char> visited; // Keep track of visited nodes
    std::stack<char> stack; // Use a stack

    stack.push(startNode); // Add the starting node

    std::cout << "DFS Traversal (Iterative): ";
    while (!stack.empty()) {
        char node = stack.top(); // Get the top node
        stack.pop(); // Remove the top node

        if (visited.find(node) == visited.end()) {
            visited.insert(node);
            std::cout << node << " "; // Process the node

            // Add neighbors to the stack in reverse order to maintain DFS order
            std::vector<char> neighbors = graph.adjList[node];
            for (int i = neighbors.size() - 1; i >= 0; i--) {
                char neighbor = neighbors[i];
                if (visited.find(neighbor) == visited.end()) {
                    stack.push(neighbor);
                }
            }
        }
    }
    std::cout << std::endl;
}

int main() {
    Graph graph;
    graph.addVertex('A');
    graph.addVertex('B');
    graph.addVertex('C');
    graph.addVertex('D');
    graph.addVertex('E');
    graph.addVertex('F');

    graph.addEdge('A', 'B');
    graph.addEdge('A', 'C');
    graph.addEdge('B', 'D');
    graph.addEdge('B', 'E');
    graph.addEdge('C', 'F');
    graph.addEdge('E', 'F');

    dfsIterative(graph, 'A');

    return 0;
}

Here’s how you might use this function:

DFS Traversal (Iterative): A C F B E D

We initialize a visited set and a stack.
We push the startNode onto the stack.
The while loop continues as long as there are nodes in the stack.
Inside the loop, we get a node from the top of the stack using stack.top() and remove it from the stack using stack.pop(). This is the node we’ll explore next.
If the node hasn’t been visited, we mark it as visited and process it.
We find all neighbors of the current node. For each neighbor that hasn’t been visited yet, we push it to the stack.
Note that we are iterating the neighbors in reversed order so that the visit sequence match closer to the recursive version of DFS.

Choosing Between Recursive and Iterative

Recursive DFS: Is often simpler to write and understand, closely matching the definition of DFS. However, it can lead to a stack overflow error if the graph is very deep.
Iterative DFS: Is more robust against deep graphs, as it uses heap memory for the stack. The logic might feel slightly less direct than recursion.

Both implementations have a time complexity of O(V + E), where V is the number of vertices (nodes) and E is the number of edges. The space complexity is O(V) in the worst case, as we need to store all vertices in the visited set and the stack (in the iterative version) or the call stack (in the recursive version). You can refer to this article to dive deeper into the time and space complexity of DFS.

What’s Next?

Now that you’ve learned how to implement DFS in C++, you can explore other related articles:

Implementing DFS in other programming languages: DFS in Python, DFS in JavaScript, DFS in Java:
Applications of DFS: Learn about the various problems DFS can solve, like finding connected components, cycle detection, and topological sorting.
Common DFS Mistakes: Understand frequent errors in DFS implementations and how to avoid them.
DFS Visualization: See DFS in action with visual examples and animations to build intuition.