Traversing a Graph using Depth First Traversal

Earlier we have seen how to build a simple Graph using Adjacency List and how to traverse it using breadth first traversal. The Graph which was used is presented below.

Building on that we are going to see how to traverse that Graph using another popular approach known as \”depth first traversal\”, or DFT. This video acts as a supplement to this article.

At the end of this Post I have presented code written in C to show you how can DFS be implemented. After all we should be able to write the code and not just talk about the approach.

A popular application of depth first traversal is to do Topological Sorting or Ordering.

Understanding DFT

In DFT we pick a vertex to start with. In our example friendship graph we start with Ankur. We visit this and mark it as visited.

Next we explore the adjacent vertices to this vertex, like Reena. But we don\’t explore the next adjacent vertex to Ankur i.e. Dikshit, instead we explore further and visit Nidhi, who is connected to Reena. So what we are doing is traversing the depths till we reach a leaf or a node that has been visited. Then we backtrack and start exploring the next adjacent node i.e. Dikshit.

Doesn\’t this sound recursive? It is and as you will see our code makes use of recursion to perform DFT.

Let\’s see the code to implement this. It\’s available at Github The method of interest here is DFS() which does the job of traversing our friendship graph.

#include<stdio.h>
#include<stdlib.h>

/*
	Author: @ankur
	Date: March 25, 2018
	Version: 0.1
	This Program illustrates Depth First Traversal.  
*/

#define MAXV 6 /* maximum number of vertices */
#define VISITED 1

/*Structure for Vertex*/
struct node{
	int label; /*data*/
	char *name; /*data*/
	int status;	
	struct node *next; /*Pointer to next node*/
};

struct node vertices[MAXV];
char *names[MAXV];

void addToList(struct node *x, int data);
void traverseGraph();
void initNames();
void displayNames();
void DFS(struct node *t);

int main(){
	/*Initialize Names*/
	initNames();
	displayNames();
	
	/*Initialize the Array*/
	for(int i=0;i<MAXV;i++){
		vertices[i].label = i;
		vertices[i].name = names[i];
		vertices[i].next = NULL;
	}
	/*
		Say we have the following Edges {(0,1), (0,2), (1,2)}
		Let\'s build the Adjacency List.
	*/
	
	addToList(&vertices[0], 1);
	addToList(&vertices[0], 3);
	addToList(&vertices[1], 2);
	addToList(&vertices[1], 0);
	addToList(&vertices[1], 4);
	addToList(&vertices[2], 1);
	addToList(&vertices[3], 0);
	addToList(&vertices[3], 5);
	addToList(&vertices[4], 1);
	
	/*Traverse the Adjacency List*/
	traverseGraph();
	/*Depth First Traversal*/
	printf(\"\\n\\n---------------DFS Traversal---------------\\n\\n\");
	DFS(&vertices[0]);
	printf(\"\\n\");
	return 0;
}

/*Here we are trying to add an edge x->y*/
void addToList(struct node *x, int data){
	printf(\"Going to Add %d to the Vertex %d \\n\", data, x->label);
	struct node *y = (struct node *)(malloc(sizeof(struct node)));
	if(y!=NULL){
		y->label = data;
		y->name = names[data];
		if(x->next != NULL)
			y->next = x->next;
		else
			y->next = NULL;
		
		x->next = y;
	}
}

void traverseGraph(){
	printf(\"\\nLet\'s see who all are Friends \\n\\n\");
	for(int i=0;i<MAXV;i++){
		struct node *temp = &vertices[i];
		printf(\"%s is friend to --> \", temp->name);
		if(temp->next != NULL){
			temp = temp->next;
			while(temp != NULL){
				printf(\"%s\", temp->name);
				if(temp->next != NULL)
					printf(\", \");
				temp = temp->next;
			}			
		}
		printf(\"\\n\\n---------------------------------------------\\n\\n\");
	}
}

void initNames(){
	names[0] = \"Ankur\";
	names[1] = \"Dikshit\";
	names[2] = \"Mohan\";
	names[3] = \"Nidhi\";
	names[4] = \"Reena\";
	names[5] = \"Suresh\";
}

void displayNames(){
	printf(\"\\nWe have the following folks staying in a small town \\n\\n\");
	for(int i=0;i<MAXV;i++){
		printf(\"%s \", names[i]);
	}
	printf(\"\\n\\n---------------------------------------------\\n\\n\");
}

void DFS(struct node *qn){
	if(qn && qn->status != VISITED){
		qn->status = VISITED;
		printf(\"Visited %s\\n\", qn->name);	
		if(qn->next != NULL){
			/*for each vetrex adjacent to v do BFS*/
			qn = qn->next;
			while(qn != NULL){
				DFS(&vertices[qn->label]);	
				qn = qn->next;
			}			
		}				
	}else{
		return;
	}	
}

When you run this the expected output is