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[10][10],visited[10],n;    //n is no of vertices and graph is sorted in array G[10][10]
 
void main()
{
    int i,j;
    printf("Enter number of vertices:");
   
	scanf("%d",&n);
 
    //read the adjecency matrix
	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[20];   
//heads of linked list
int visited[20];
int n;
void read_graph(); 
//create adjacency list
void insert(int,int);  
//insert an edge (vi,vj) in te adjacency list
void DFS(int);
 
void main()
{
    int i;
    read_graph();
    //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;
    }
}
 
void read_graph()
{
    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: