Depth First Search (DFS) Traversal in C++

DFS is a powerful graph traversal technique that explores a path as deeply as possible before backtracking. It is one of the most fundamental algorithms used in graph theory, and understanding it opens the door to solving a variety of problems like cycle detection, connected components, and more.

Depth First Search (DFS) Traversal on Graph

class Solution {
  public:
  void trav(vector<vector<int>>& adj,vector<bool>& vis,vector<int>& t,int i){
      vis[i]=true;
      t.push_back(i);
      for(int j=0;j<adj[i].size();j++){
          int nex=adj[i][j];
          if(!vis[nex]){
              trav(adj,vis,t,nex);
          }
      }
  }
    vector<int> dfs(vector<vector<int>>& adj){
        int n=adj.size();
        vector<bool> vis(n,false);
        vector<int> t;
        trav(adj,vis,t,0);
        return t;
    }
};

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

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

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

 Input

Adjacency List:
0 → 1, 2 
1 → 0 
2 → 0
Output
0 1 2

How It Works

DFS starts from node 0, visits its first unvisited neighbor, and keeps going deeper. Once it can’t go further, it backtracks to the previous node and explores any remaining neighbors. The process continues until all reachable nodes are visited.

Time and Space Complexity

• Time Complexity: O(V + E)

• Space Complexity: O(V)