Depth First Search (DFS) for a Graph

Depth First Search is a traversing or searching algorithm in tree/graph data structure. The concept of backtracking we use to find out the DFS. It starts at a given vertex (any arbitrary vertex) and explores it and visit the any of one which is connected to the current vertex and start exploring it. Repeat this step till we got a vertex having no connected nodes and then use backtracking and goto the previously visited vertex which is stored in a stack. Use the concept of backtracking until we visit all vertices(stack is not empty).

Note: We use the STACK type data structure to implement the above logic by storing the visited vertices.

Table of Contents

Step by step explanation of Depth First Search (DFS)

NOTE:

There is more than one DFS possible for a particular graph(like the above graph). Like some other possible DFS for the above graph are (1,3,4,5,7,62), (1,2,3,4,7,5,6)….
In the binary tree, the Inorder, Preorder, and Postorder traversal comes under DFS traversal.

Implementation of DFS

C++ Program for Depth First Search

/*C++ Implementation of the DFS for a given graph using STL.*/
#include <bits/stdc++.h>
using namespace std;
int main() {
  int nodes,edges;
  /*take input*/
  cin>>nodes>>edges;
  vector<int> v[nodes+1];
  bool visited [nodes+1];
  /*initalise all vertices as false(unvisited)*/
  memset(visited,false,sizeof(visited));
  /*make graph using vector*/
  for(int i=0;i<edges;i++)
  {
      int x,y;
      cin>>x>>y;
      /*add edge between x and y*/
      v[x].push_back(y);
      /*add edge between y and x*/
      v[y].push_back(x);
  }
  int start;
  /*Take input node at which the DFS starts*/
  cin>>start;
  stack<int> s;
  /*Push the vertex at which the DFS start*/
  s.push(start);
  /*vector use to store the answer*/
  vector<int> dfs;
  /*perform the operation till the size of stack is not empty*/
  while(!s.empty())
  {
      int top=s.top();
      s.pop();
      /*if the vertex is not visited then add it to dfs*/
      if(visited[top]==false)
      {
          visited[top]=true;
           dfs.push_back(top);
      }
      /*explore the current vertex*/
      for(int  i=0;i<v[top].size();i++)
      {
          if(visited[v[top][i]]==false)
          {
              s.push(v[top][i]);
          }
      }
  }
  /*print the DFS for given graph at starting with given node*/
  for(int i=0;i<nodes;i++)
  {
      cout<<dfs[i]<<" ";
  }
  cout<<"\n";
  return 0;
}

Output: 
1 3 4 7 6 5 2

Time Complexity of Depth First Search (DFS)

O(V+E) where V is the number of vertices and E is the number of edges.

Reference

Interview Questions