Depth First Search (DFS) Traversal of a Graph in C++

Depth First Search (DFS) is one of the most commonly used algorithms in graph theory. It’s used to explore all the vertices and edges of a graph systematically, and is a fundamental building block for many advanced problems in computer science.

In this blog, we’ll write a simple and clean C++ program to perform DFS traversal on a graph using an adjacency list.

Depth First Search (DFS) Traversal of a Graph in C++

What Is DFS?

DFS explores as deep as possible along a branch before backtracking. It uses recursion (or a stack) to track the visited nodes.

---

 Problem Statement

Given an undirected graph represented as an adjacency list, perform a DFS traversal starting from node 0.

---

 Input Format

The graph will be represented as an adjacency list using a vector of vectors.

Example:

#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    void dfs1(vector<vector<int>>& adj,vector<bool>& vis,vector<int>& ans,int ind){
        vis[ind]=true;
        ans.push_back(ind);
        for(int i=0;i<adj[ind].size();i++){
            if(!vis[adj[ind][i]]){
                dfs1(adj,vis,ans,adj[ind][i]);
            }
        }
    }

    vector<int> dfs(vector<vector<int>>& adj) {
        int n=adj.size();
        vector<bool> vis(n,false);
        vector<int> ans;
        dfs1(adj,vis,ans,0);
        return ans;
    }
};

int main() {
    vector<vector<int>> adj={
        {1, 2},
        {0},
        {0}
    };

    Solution obj;
    vector<int> result=obj.dfs(adj);

    cout<< "DFS Traversal: ";
    for(int i=0;i<result.size();i++) {
        cout<<result[i]<<" ";
    }
    cout<<endl;

    return 0;
}

Input

Graph (Adjacency List):

---

 Output