Depth First Search

Graph

Share

In this tutorial we are learning about Depth First Search (DFS) for a graph. The graph 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.

Adj0123
0
1
2
3

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.

Adj0123
00100
10111
21001
30010

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[STACK_SIZE];
	
	//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.