Algorithms in C - Depth First Search

Posted on April 14, 2016
algorithms-in-c-depth-first-search

In this part of Algorithms in C tutorial series, I will explain what is Depth First Search and I will show you - how to write a Depth First Search from scratch in C. Depth First Search is one of the very important Algorithms. Many programming problems are efficiently solved using Depth First Search or DFS. This is often asked in interviews.


Depth First Search is implemented using recursion. Suppose S is the source node from which you would like to do the Depth First Search.


We then mark this node and recursively compute the DFS on it's unmarked children.


Let's take the example of the following undirected Graph.



Let's start the DFS from the Node 1. Node 1 has neighbors Node 2 and Node 4. Both of them are unmarked. We mark Node 1 and say we start the DFS from the Node 2.

Node 2 has two neighbors - Node 1 and Node 3. Node 1 is already marked. Therefore, we mark Node 2 and we start the DFS from Node 3.


Node 3 has three neighbors - Node 2, Node 4 and Node 5. Node 2 is already marked. But Node 4 and Node 5 are unmarked. Therefore, we mark Node 3 and we start the DFS from say - Node 5.


Node 5 has only one neighbor Node 3 and Node 3 is already marked. Therefore, we mark Node 5 and just go back to the parent, Node 3. Node 3 has one more unmarked node - Node 4. Therefore, we again start our DFS on Node 4.


Node 4 does not have any unmarked neighboring node. Therefore, we simply mark Node 4 and come back to the parent, Node 3. Now, Node 3 also does not have any unmarked neighbors. Therefore, we come back to the parent of Node 3 which is Node 2.


Node 2 also does not have any unmarked neighbor and we come back to the parent of Node 2 which is Node 1. Node 1 also does not have any unmarked neighbor and the DFS ends.


Below is the complete working code for Depth First Search Algorithms in C using Adjacency List and recursion . I have taken Nodes as integer. You can modify the code to change the data types of the Nodes as per your requirement.


#include <stdio.h>
#include <stdlib.h>
struct Graph{
int V;
int E;
struct list **Adj;
};
struct list{
int v;
struct list *next;
int marked;
};
struct Graph *createGraph(int V){
int i;
struct Graph *G = (struct Graph*)malloc(sizeof(struct Graph));
G->V=V;
G->Adj = (struct list**)malloc(sizeof(struct list*)*V);
for(i=0;i<V;i++){
G->Adj[i]=(struct list*)malloc(sizeof(struct list));
G->Adj[i]->v=i;
G->Adj[i]->next=NULL;
G->Adj[i]->marked = 0;
}
return G;
}
void DFS(struct Graph *G, int i, int *A,int *index){
struct list *head = G->Adj[i];
if(head->marked)
return;
head->marked = 1;
A[*index]= i;
(*index)= (*index) + 1;
head= head->next;
while(head){
DFS(G,head->v,A, index);
head = head->next;
}
}
int main()
{
int i,V,E,u,v;
int component = 0, index =0;
printf("Enter # of nodes : ");
scanf("%d",&V);
printf("\nEnter # of edges : ");
scanf("%d",&E);
struct Graph *G=createGraph(V);
G->E = E;
int *A=(int *)malloc(sizeof(int)*V);
printf("\nNote - Node numbers shall start from 0\n\n");
for(i=0;i<G->E;i++){
printf("Nodes for edge # %d : ",i+1);
scanf("%d%d",&u,&v);
struct list *newNode = (struct list*)malloc(sizeof(struct list));
newNode->v=v;
newNode->next = G->Adj[u]->next;
G->Adj[u]->next = newNode;
}
for(i=0;i<G->V;i++){
struct list *head = G->Adj[i];
if(head->marked)
continue;
component++;
index = 0;
DFS(G,i,A,&index);
printf("DFS order for component # %d is\n",component);
int j =0;
for(j=0;j<index;j++)
printf("%d ",A[j]);
}
return 0;
}


You may have noticed that I am computing the DFS traversal component wise. Because - in case of disconnected Graph, you will have the Graph split into different components.


In that case you have to individually compute the DFS for each component.


If you have any doubt regarding the code or any other concept, please leave your queries in the comment section.

Sharing is Caring!

GET FREE UPDATES


RECOMMENDED POSTS FOR YOU


profile image

Kaushik Baruah

Research Engineer @XRCI


ABOUT

My name is Kaushik Baruah and I am the chief blogger on this Blog and here I like to share my experience as software engineer and research engineer with my online readers. I will try to focus on career planning, latest emerging technologies and tutorials on various computer science subjects. You can follow me on Twitter, Facebook and Google+

GET FREE UPDATES

POPULAR POSTS

Copyright © 2016
About Us

My name is Kaushik Baruah and I am the chief blogger on this Blog and here I like to share my experience as software engineer and research engineer with my online readers. I will try to focus on career planning, latest emerging technologies and tutorials on various computer science subjects.

Get Free Updates