# Depth First Search (DFS) Program in C

In this instructional exercise, you will find out about the Depth First Search (DFS) program in C with calculation.

The vast majority of diagram issues include traversal of a chart. Traversal of a diagram means visiting every hub and visiting precisely once. There are two kinds of traversal in diagrams, for example, Profundity First Search (DFS) and Breadth-First Search (BFS).

It resembles a tree. Traversal can begin from any vertex, state Vi. Vi is visited and afterwards all vertices nearby Vi are navigated recursively utilizing DFS. Since a chart can have cycles. We should abstain from returning to a hub.

To do this, when we visit a vertex V, we mark it visited. A hub that has just been set apart as visited ought not to be chosen for traversal.

Checking of visited vertices should be possible with the assistance of a worldwide cluster visited[ ]. Exhibit visited[ ] is instated to false (0).

Profundity First Search (DFS) Algorithm

``````n ← number of nodes
Initialize visited[ ] to false (0)
for(i=0;i<n;i++)
visited[i] = 0;

void DFS(vertex i) [DFS starting from i]
{
visited[i]=1;
for each w adjacent to i
if(!visited[w])
DFS(w);
}``````

The diagram appeared above is taken as a contribution to both the projects referenced beneath:

Profundity First Search (DFS) Program in C [Adjacency Matrix]

``````#include<stdio.h>

void DFS(int);
int G,visited,n;    //n is no of vertices and graph is sorted in array G

void main()
{
int i,j;
printf("Enter number of vertices:");

scanf("%d",&n);

printf("\nEnter adjecency matrix of the graph:");

for(i=0;i<n;i++)
for(j=0;j<n;j++)
scanf("%d",&G[i][j]);

//visited is initialized to zero
for(i=0;i<n;i++)
visited[i]=0;

DFS(0);
}

void DFS(int i)
{
int j;
printf("\n%d",i);
visited[i]=1;

for(j=0;j<n;j++)
if(!visited[j]&&G[i][j]==1)
DFS(j);
}``````

Output

Profundity First Search (DFS) Program in C [Adjacency List]

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

typedef struct node
{
struct node *next;
int vertex;
}node;

node *G;
int visited;
int n;
void insert(int,int);
//insert an edge (vi,vj) in te adjacency list
void DFS(int);

void main()
{
int i;
//initialised visited to 0

for(i=0;i<n;i++)
visited[i]=0;

DFS(0);
}

void DFS(int i)
{
node *p;

printf("\n%d",i);
p=G[i];
visited[i]=1;
while(p!=NULL)
{
i=p->vertex;

if(!visited[i])
DFS(i);
p=p->next;
}
}

{
int i,vi,vj,no_of_edges;
printf("Enter number of vertices:");

scanf("%d",&n);

//initialise G[] with a null

for(i=0;i<n;i++)
{
G[i]=NULL;
//read edges and insert them in G[]

printf("Enter number of edges:");
scanf("%d",&no_of_edges);

for(i=0;i<no_of_edges;i++)
{
printf("Enter an edge(u,v):");
scanf("%d%d",&vi,&vj);
insert(vi,vj);
}
}
}

void insert(int vi,int vj)
{
node *p,*q;

//acquire memory for the new node
q=(node*)malloc(sizeof(node));
q->vertex=vj;
q->next=NULL;

//insert the node in the linked list number vi
if(G[vi]==NULL)
G[vi]=q;
else
{
//go to end of the linked list
p=G[vi];

while(p->next!=NULL)
p=p->next;
p->next=q;
}
}``````

Output

On the off chance that you discovered anything erroneous or have questions with respect to above Depth First Search (DFS) program in C instructional exercise at that point remark underneath.

Here is a Tutorial with a line-by-line code to help you understand it easily: