## 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.

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!

RECOMMENDED POSTS FOR YOU