Depth First Search (DFS) algorithm is used to traverse a graph depthward motion. DFS Algorithm use data structure stack to remember to get the next vertex to start the search and we will requred an array to keep the track of vertex that it is visited or unvisited.

In DFS traversal we look start from the sorce, then we look for the adjacent unvisited vertices of the source. We display them, mark them visited and put them into the stack. If there is not remain any adjacent vertex which is unvisited. Then, we popped out the top element of the stack and do the same for the popped out element. We will repeat the same till the stack becomes empty.

Algorithm:

 

1. Mark all the vertices unvisited
2. set: source=vertex from where we want to start DFS traversal
3. let vertex_status[]
       #This array is used to track that the vertex is vistied or not
4. let graph_matrix[][] is the adj_matrix of graph having n nodes
        
       #if ith and jth node is connected then graph_matrix[i][j]=1
         else graph_matrix[i][j]=0

5. Display the source vertex and mark it as visited.
6. push the sourve vertex to the STACK
7. do While STACK is not empty:
8.      set: source=STACK.top()
9.      Update Stack by pop out top element of stack
10.    do For i=1 to n:
11.     If graph_matrix[source][i]=1 and vertex_status[i]=unvisited:
12.                    Display vertex 'i' and mark it as visited
13.                    Push the vertex 'i' to the STACK
14.    EndFor
15. EndWhile

Example:
 

 
Traversal: 

Let's start the traversal in the above exam from vertex 1

Let:         source=1
Display:  source=1
Set:         vertex_status[source]=vertex_status[1]=visited
Do:         que.push(source) /* pushing the source vertex in STACK */

                 Output                                 Updated  Stack                                       Visited Vertex

                 1                                            1                                                                1

Now do While Stack is not empty

Pass   1:        

Pop out first element of stack that is 1, and look for adjacent unvisited vertices of the vertex 1, which are 2 and 5. Now display 2 and 5 and put them into the stack. Updated table is given below.             

                Output                                 Updated  Stack                                        Visited Vertex

                1 2 5                                     top-> 5 2 <-bottom                                  1 2 5

Pass   2:  

Pop out the first element of stack and which is 5 and look for the adjacent unvisited vertices of vertex 5 and which is only 4 because 2 and 1 is already visited. Now displayand put it into the stack. Updated table is given below.

                Output                                 Updated  Stack                                       Visited Vertex

                1 2 5 4                                  top-> 4 2 <-bottom                                 1 2 5 4

Pass   3:  

Pop out the first element of stack and which is 4 and look for the adjacent unvisited vertices of vertex 4 which are 3 and 6 because 5 is already visited. Now display 3 and 6, mark them visited  and put them into the stack. Updated table is given below.

               Output                                 Updated  Stack                                      Visited Vertex

               1 2 5 4 3 6                            top-> 6 3 2 <-bottom                            1 2 5 4 3 6                                   

Pass   4:  

Pop out the top element of stack and which is 6 and look for the adjacent unvisited vertices of vertex 6 but there is no any unvisited adjacent vertex due to which no element is displayed. Updated table is given below.

               Output                                 Updated  Stack                                      Visited Vertex

               1 2 5 4 3 6                            top-> 3 2 <-bottom                                1 2 5 4 3 6

Pass   5:  

Pop out the top element of stack and which is 3 and look for the adjacent unvisited vertices of vertex but there is no any unvisited adjacent vertex due to which no element is displayed. Updated table is given below.

               Output                                 Updated  Stack                                      Visited Vertex

               1 2 5 4 3 6                            top-> 2 <-bottom                                   1 2 5 4 3 6 

Pass   6:  

Pop out the first element of stack and which is 2 and look for the adjacent unvisited vertices of vertex 2. Therefore no element will be displayed.

               Output                                 Updated Stack                                        Visited Vertex

               1 2 5 4 3 6                                                                                              1 2 5 4 3 6

Now stack becomes empty therefore while loop will terminate.

Implementation of the above Algorithm in C++

 


#include <stdio.h>
#include <stack>
#define MAX 100
#define visited 2
#define unvisited 1
using namespace std;

class dfs_traversal
{
   private:
        std::stack <int> s;
        int vertex_status[MAX],graph_matrix[MAX][MAX];
        int n;
      public:
           void get_data();
           void dfs_traverse();
};
void dfs_traversal::get_data()
{
   printf("\nEnter the total number of vertices: ");
   scanf("%d",&n);
   int max_edge=n*(n-1)/2;
   int i,source,destination;
   for(i=1;i<=max_edge;i++)
   {
            printf("\nEnter the source and destination of edge %d and (0,0) to Exit:\n",i);
            scanf("%d%d",&source,&destination);
            if(source==0 && destination==0)
            {
                  break;
            }
            else
            {
                  graph_matrix[source][destination]=1;
                  graph_matrix[destination][source]=1;
            }
   }
}
void dfs_traversal::dfs_traverse()
{
     /* Marking all vertices unvisited */

      int i;
      for(i=1;i<=n;i++)
      {
            vertex_status[i]=unvisited;
      }
      int source;
      printf("\nEnter the source to start dfs traversal of graph: \n");
      scanf("%d",&source);
      printf("\n%d ",source);
      vertex_status[source]=visited;
      s.push(source);
      while(!s.empty())
      {
             source=s.top();
             s.pop();
             for(i=1;i<=n;i++)
             {
                   if(graph_matrix[source][i]==1 && vertex_status[i]==unvisited)
                   {
                         printf("%d ",i);
                         vertex_status[i]=visited;
                         s.push(i);
                   }
             }
      }
}
int main()
{
      dfs_traversal graph;
      graph.get_data();
      graph.dfs_traverse();
      return 0;
}

OUTPUT:
 

 

See also: C++ Program to traverse a graph using BFS