Program to implement Depth First Search/traversal in C 

We will be using the following graph :

As we know that the dfs of a graph is similar to the dfs of a tree with the only difference that the graph may have cycles too.

We will be using the same approach as in tree, We start from the starting and traverse its leftmost or rightmost children first and and then its children and so on before traversing its sibling nodes but as we are traversing a graph a node may have link to the already visited node that creates the cycle so that node may be repeated again and this process will continue on ..so inorder to avoid this ambiguity, we will be using an array "visited" to keep track of all nodes that are visited.

We will be using recursion to print all the nodes of the graph. We will first print the starting node then all its adjacent like nodes as passed on the recursive function unlike binary trees where we pass only tree->left and tree->right , Here we will pass all its adjacent elements from its adjaceny list and so on.

Below is the C implementation of the same:

#include<stdio.h>
#include<stdlib.h>
int visited[10]={0,0,0,0};  //take it to the no of nodes in graph ,or allocate memory dynamically
struct node
{
    int a;
    struct node * next;
};
struct graph
{
    int v;
    struct node **array;
};
void addedge(struct graph *g,int s,int d)
{
    struct node*temp ;
    temp= (struct node *)malloc(sizeof(struct node));
    temp->a=d;
    temp->next=g->array[s];// adding the node at the starting of the list
    g->array[s]=temp;
}
void dfs(int x,struct graph *g)
{
struct node *temp;
   if(visited[x]==0)
   {
       printf("%d",x);
       visited[x]=1;

temp=g->array[x];
while(temp)
{
    dfs(temp->a,g);
    temp=temp->next;
}
   }
   return;
}

int main()
{
struct graph *g;
g=(struct graph *)malloc(sizeof(struct graph));
g->v=4;
g->array=(struct node **)malloc(5*sizeof(struct node*));
int i;
for(i=0;i<4;i++) //intializing the graph
{
    struct node *n;
    n= (struct node*)malloc(sizeof(struct node));
    n->a=i;
    n->next=NULL;
    g->array[i]=n;
}
addedge(g,0,1); //Creating the graph first here
addedge(g,0,2);
addedge(g,1,2);
addedge(g,2,3);
addedge(g,2,0);
addedge(g,3,3);
printf("DFs=\n");
dfs(2,g);
return 0;
}

Output: