Home / C / C program for dfs – Depth First Search

C program for dfs – Depth First Search

This is a c program for DFS – depth first search In which the the searching goes on to all the siblings first rather than the nodes i.e the first item searched is the leftmost leaf node. Moreover you have to enter the number of nodes in the graph and the adjacency matrix. Though leftmost node is searched still extra provision has been made here you have been asked for which node you want to search first ” starting node ” in DFS.

#include<stdio.h>
#include<conio.h>
void dfs(int v);
typedef enum boolean{false,true}bool;
int n,a[10][10];
bool visited[10];
void main()
{
int i,j,v;
printf("Enter the no. of nodes in the graph\n");
scanf("%d",&n);
printf("Enter the adjacency matrix \n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
scanf("%d",&a[i][j]);
}
}
printf("The adjacency matrix shown as\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("%d ",a[i][j]);
}
printf("\n");
}
printf("Enter the starting node for Depth First search\n");
scanf("%d",&v);
for(i=1;i<=n;i++)
visited[i]=false;
dfs(v);
getch();
}
void dfs(int v)
{
int i,stack[10],top=-1,pop;
top++;
stack[top]=v;
while(top>=0)
{
pop=stack[top];
top--;
if(visited[pop]==false)
{
printf("%d",pop);
visited[pop]=true;
}
else
continue;
for(i=n;i>=1;i--)
{
if(a[pop][i]==1 && visited[i]==false)
{
top++;// push all the unvisited neighbours in the stack
stack[top]=i;
}
}
}
}

OUTPUT:

c program for DFS

Incoming Terms: dfs, depth first search, c program for dfs

 

Check Also

Restrict Mouse Pointer Position C Graphics Program

This C Program will restrict the Mouse Pointer location or to a particular position or x,y ...

Leave a Reply

Your email address will not be published. Required fields are marked *

Preventing spam * Time limit is exhausted. Please reload the CAPTCHA.