C++ Program to Implement Depth-First Search (DFS)

Graph traversal is a fundamental concept in computer science, helping programmers explore data structures and networks efficiently. Depth-First Search (DFS) is a popular graph traversal algorithm that starts at a root node and explores as far as possible along each branch before backtracking. Unlike simple searches, DFS dives deep into one path, making it ideal for problems like pathfinding, maze solving, and cycle detection. For beginners, understanding DFS helps strengthen the grasp of recursion, stacks, and graph representation.

DFS is widely used in real-world applications such as web crawling, social network analysis, and AI game development. By learning DFS in C++, you also gain insight into how recursion and data structures work together to solve complex problems efficiently. Its simplicity in concept but depth in application makes it a perfect starting point for anyone exploring graph algorithms.

Table of Contents

Toggle

Program 1: Recursive DFS on an Undirected Graph
Program 2: Iterative DFS Using a Stack
Program 3: DFS on a Directed Graph
Program 4: DFS to Detect Connected Components
Frequently Asked Questions (FAQ)
Conclusion

Program 1: Recursive DFS on an Undirected Graph

This program demonstrates the classic recursive DFS using an adjacency list with a predefined graph.

#include <iostream>
#include <vector>

using namespace std;

void dfsRecursive(int node, vector<vector<int>> &adj, vector<bool> &visited) {

    visited[node] = true;

    cout << node << " ";

    for (int neighbor : adj[node]) {

        if (!visited[neighbor]) {
            dfsRecursive(neighbor, adj, visited);
        }

    }

}

int main() {

    int nodes = 5;
    vector<vector<int>> adj(nodes);

    adj[0] = {1, 2};
    adj[1] = {0, 3, 4};
    adj[2] = {0};
    adj[3] = {1};
    adj[4] = {1};

    vector<bool> visited(nodes, false);

    cout << "DFS Traversal starting from node 0: ";

    dfsRecursive(0, adj, visited);
    cout << endl;

    return 0;

}

#include <iostream>
#include <vector>

using namespace std;

void dfsRecursive(int node, vector<vector<int>> &adj, vector<bool> &visited) {

    visited[node] = true;

    cout << node << " ";

    for (int neighbor : adj[node]) {

        if (!visited[neighbor]) {
            dfsRecursive(neighbor, adj, visited);
        }

    }

}

int main() {

    int nodes = 5;
    vector<vector> adj(nodes);

    adj[0] = {1, 2};
    adj[1] = {0, 3, 4};
    adj[2] = {0};
    adj[3] = {1};
    adj[4] = {1};

    vector visited(nodes, false);

    cout << "DFS Traversal starting from node 0: ";

    dfsRecursive(0, adj, visited);
    cout << endl;

    return 0;

}

In this example, DFS visits node 0, then dives as deep as possible into each branch before backtracking. Beginners can see how recursion naturally handles the traversal and how the adjacency list makes it easy to explore neighbors.

Program 2: Iterative DFS Using a Stack

This program demonstrates DFS without recursion, using a stack to manage the traversal.

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

void dfsIterative(int start, vector<vector<int>> &adj) {

    vector<bool> visited(adj.size(), false);
    stack<int> s;

    s.push(start);

    while (!s.empty()) {

        int node = s.top();
        s.pop();

        if (!visited[node]) {
            visited[node] = true;
            cout << node << " ";
        }

        for (auto it = adj[node].rbegin(); it != adj[node].rend(); ++it) {

            if (!visited[*it]) {
                s.push(*it);
            }

        }

    }

}

int main() {

    int nodes = 5;
    vector<vector<int>> adj(nodes);

    adj[0] = {1, 2};
    adj[1] = {0, 3, 4};
    adj[2] = {0};
    adj[3] = {1};
    adj[4] = {1};

    cout << "Iterative DFS starting from node 0: ";

    dfsIterative(0, adj);
    cout << endl;

    return 0;

}

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

void dfsIterative(int start, vector<vector<int>> &adj) {

    vector visited(adj.size(), false);
    stack s;

    s.push(start);

    while (!s.empty()) {

        int node = s.top();
        s.pop();

        if (!visited[node]) {
            visited[node] = true;
            cout << node << " ";
        }

        for (auto it = adj[node].rbegin(); it != adj[node].rend(); ++it) {

            if (!visited[*it]) {
                s.push(*it);
            }

        }

    }

}

int main() {

    int nodes = 5;
    vector<vector> adj(nodes);

    adj[0] = {1, 2};
    adj[1] = {0, 3, 4};
    adj[2] = {0};
    adj[3] = {1};
    adj[4] = {1};

    cout << "Iterative DFS starting from node 0: ";

    dfsIterative(0, adj);
    cout << endl;

    return 0;

}

Using a stack instead of recursion gives beginners a better understanding of how DFS can be implemented iteratively. It also highlights how the last-in-first-out (LIFO) property mimics the recursive call stack.

Program 3: DFS on a Directed Graph

This program applies DFS to a directed graph, which is useful for tasks like topological sorting and detecting cycles.

#include <iostream>
#include <vector>

using namespace std;

void dfsDirected(int node, vector<vector<int>> &adj, vector<bool> &visited) {

    visited[node] = true;

    cout << node << " ";

    for (int neighbor : adj[node]) {

        if (!visited[neighbor])
            dfsDirected(neighbor, adj, visited);

    }

}

int main() {

    int nodes = 4;
    vector<vector<int>> adj(nodes);

    adj[0] = {1, 2};
    adj[1] = {2};
    adj[2] = {3};
    adj[3] = {};

    vector<bool> visited(nodes, false);

    cout << "DFS on directed graph starting from node 0: ";

    dfsDirected(0, adj, visited);
    cout << endl;

    return 0;

}

#include <iostream>
#include <vector>

using namespace std;

void dfsDirected(int node, vector<vector<int>> &adj, vector<bool> &visited) {

    visited[node] = true;

    cout << node << " ";

    for (int neighbor : adj[node]) {

        if (!visited[neighbor])
            dfsDirected(neighbor, adj, visited);

    }

}

int main() {

    int nodes = 4;
    vector<vector> adj(nodes);

    adj[0] = {1, 2};
    adj[1] = {2};
    adj[2] = {3};
    adj[3] = {};

    vector visited(nodes, false);

    cout << "DFS on directed graph starting from node 0: ";

    dfsDirected(0, adj, visited);
    cout << endl;

    return 0;

}

This example shows that DFS works for both undirected and directed graphs. Beginners can learn that traversal order may differ depending on graph direction and edge arrangement.

Program 4: DFS to Detect Connected Components

Here, DFS is used to count connected components in an undirected graph, illustrating a practical application.

#include <iostream>
#include <vector>

using namespace std;

void dfsComponents(int node, vector<vector<int>> &adj, vector<bool> &visited) {

    visited[node] = true;

    for (int neighbor : adj[node]) {

        if (!visited[neighbor])
            dfsComponents(neighbor, adj, visited);

    }

}

int main() {

    int nodes =    6;
    vector<vector<int>> adj(nodes);

    adj[0] = {1};
    adj[1] = {0, 2};
    adj[2] = {1};
    adj[3] = {4};
    adj[4] = {3};
    adj[5] = {};

    vector<bool> visited(nodes, false);
    int components = 0;

    for (int i = 0; i < nodes; i++) {

        if (!visited[i]) {
            dfsComponents(i, adj, visited);
            components++;
        }

    }

    cout << "Number of connected components: " << components << endl;

    return 0;

}

#include <iostream>
#include <vector>

using namespace std;

void dfsComponents(int node, vector<vector<int>> &adj, vector<bool> &visited) {

    visited[node] = true;

    for (int neighbor : adj[node]) {

        if (!visited[neighbor])
            dfsComponents(neighbor, adj, visited);

    }

}

int main() {

    int nodes =    6;
    vector<vector> adj(nodes);

    adj[0] = {1};
    adj[1] = {0, 2};
    adj[2] = {1};
    adj[3] = {4};
    adj[4] = {3};
    adj[5] = {};

    vector visited(nodes, false);
    int components = 0;

    for (int i = 0; i < nodes; i++) {

        if (!visited[i]) {
            dfsComponents(i, adj, visited);
            components++;
        }

    }

    cout << "Number of connected components: " << components << endl;

    return 0;

}

This example demonstrates how DFS can solve real-world problems, like identifying isolated clusters in networks. Beginners learn that DFS is more than just traversal; it is a tool for problem-solving in graph theory.

Frequently Asked Questions (FAQ)

Q1: What is Depth-First Search (DFS)?
DFS is a graph traversal algorithm that explores nodes as far as possible along each branch before backtracking.

Q2: When should I use DFS?
DFS is useful for pathfinding, cycle detection, connected components, and problems where exploring deep paths first is advantageous.

Q3: Can DFS be implemented iteratively?
Yes, DFS can use a stack to mimic recursion, which is helpful for large graphs where recursion may cause stack overflow.

Q4: Does DFS work on directed graphs?
Yes, DFS works on both directed and undirected graphs, though traversal order depends on edge direction.

Q5: What is the time complexity of DFS?
The time complexity is O(V + E), where V is the number of vertices and E is the number of edges.

Conclusion

Depth-First Search is a versatile and fundamental algorithm in graph theory. In this article, we explored recursive and iterative DFS, applied DFS to directed graphs, and used it to detect connected components. Beginners can see how DFS explores graphs deeply, backtracks when necessary, and solves practical problems.

By practicing DFS, learners gain strong foundational skills in recursion, stacks, and graph traversal. Understanding DFS is an important step toward mastering more complex algorithms like BFS, Dijkstra, and A* search. Start experimenting with different graphs and edge configurations to see DFS in action and develop a deeper intuition for graph algorithms.

Share this article

Twitter LinkedIn Facebook