Depth First Search

In this tutorial we are learning about Depth First Search algorithm.

The graph that we will consider can be both a directed graph and a non directed graph and can also contain cycles.

In DFS or Depth First Search we have to keep track of vertices that are visited in order to prevent revisiting them. For this we use an array to mark visited and unvisited vertices. In DFS we also take help of a STACK. When a vertex is visited, we push it into the stack. The process ends when the stack becomes empty.

We start the process by considering any one of the vertex as the starting vertex.

Problem

Consider the following graph.

There are 4 vertices in the graph so we will need an adjacency matrix having 4 rows and 4 columns.

Row and Column name is same as the vertex name. The cells of the adjacency matrix Adj will contain 1 if there is an edge from starting vertex to ending vertex. If there is no edge then it will contain 0.

As per the given graph our adjacency matrix will look like the following.

To keep track of the visited vertices we will use the visited[] array. The size of this array will be equal to the number of vertices in the graph. In this case it is 4.

Initially, we will set all the elements in the array visited[] as 0 which means unvisited. As we progress we will be visiting new vertices so, we will be marking the respective index in the visited[] array with 1. Note, the vertices in the graph are names from 0 to 3 so, we can use the visited[] array index to represent the respective vertex.

We will also use a stack to push and pop vertices into and out of it as we progress.

Steps

Step 1: We consider a vertex as the starting vertex, in this case vertex 3.
Step 2: We push vertex 3 into the stack.
Step 3: We set visited[3] = 1 which means we have visited vertex 3.
Step 4: Print starting vertex 3 as the first result.
Step 5: If the stack is not empty then, take the top vertex in the stack. Else STOP.
Step 6: Set i = vertex at the top of the stack.
Step 7: If visited[j] == 0 AND Adj[i][j] == 1 where j = 0 to 3, then Next result is j
Step 8: Set visited[j] = 1.
Step 9: Push j into the stack. Go to step 5.

Code

#include <stdio.h>

#define STACK_SIZE 20
#define MAX 20

void dfs(int Adj[][MAX], int n, int source);

int main(void) {
  //Adj matrix
  int Adj[][MAX] = {
    {0,1,0,0},
    {0,1,1,1},
    {1,0,0,1},
    {0,0,1,0}
  };
  
  int n = 4;  //no. of vertex
  int starting_vertex = 3;
  
  dfs(Adj, n, starting_vertex);
  
  return 0;
}

void dfs(int Adj[][MAX], int n, int source) {
  //variables
  int i, j;
  bool change = false;

  //visited array to flag the vertex that
  //were visited
  int visited[MAX];

  //top of the stack
  int tos = 0;

  //stack
  int stack[MAX];
  
  //set visited for all vertex to 0 (means unvisited)
  for(i = 0; i < MAX; i++) {
    visited[i] = 0;
  }
  
  //mark the visited source
  visited[source] = 1;
  
  //push the vertex into stack
  stack[tos] = source;
  
  //print the vertex as result
  printf("%d ", source);
  
  //continue till stack is not empty
  while(tos >= 0) {
    //to check if any vertex was marked as visited
    change = false;
    
    //get vertex at the top of the stack
    i = stack[tos];
    
    for(j = 0; j < n; j++) {
      if(visited[j] == 0 && Adj[i][j] == 1) {
        //mark vertex as visited
        visited[j] = 1;
        
        //push vertex into stack
        tos++;
        stack[tos] = j;
        
        //print the vertex as result
        printf("%d ", j);
        
        //vertex visited
        change = true;
        
        break;
      }
    }
    if(change == false) {
      tos--;
    }
  }
  printf("\n");
}

Output: 3 2 0 1

Time complexity

The time complexity of Depth First Search (DFS) is O(V+E) where, V is the total number of vertices in the graph and E is the total number of edges in the graph.