Depth First Search & Breadth First Search C Program Implementation
This is the C Program Implementation of BFS and DFS
BFS
Order in which the nodes are visited
In graph theory, breadth-first search (BFS) is a strategy for searching in a graph when search is limited to essentially two operations: (a) visit and inspect a node of a graph; (b) gain access to visit the nodes that neighbor the currently visited node. The BFS begins at a root node and inspects all the neighboring nodes. Then for each of those neighbor nodes in turn, it inspects their neighbor nodes which were unvisited, and so on. Compare BFS with the equivalent, but more memory-efficient Iterative deepening depth-first search and contrast with depth-first search.
DFS
Order in which the nodes are visited
Depth-first search (DFS) is an algorithm for traversing or searching tree or graph data structures. One starts at the root (selecting some arbitrary node as the root in the case of a graph) and explores as far as possible along each branch before backtracking.
#include<stdio.h>
int top=-1,q[20],stack[20],front=-1,rear=-1,arr[20][20],visited[20]={0};
main()
{
int i,j,n,ch,s;
printf("Enter the Number of Verticesn");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("Enter 1 if %d has a node with %d else 0n",i,j);
scanf("%d",&arr[i][j]);
}
}
printf("Enter Choice 1.BFS 2.DFS n");
scanf("%d",&ch);
printf("Enter stating vertexn");
scanf("%d",&s);
while(ch!=3)
{
switch(ch)
{
case 1:bfs(s,n);
break;
case 2:dfs(s,n);
break;
}
scanf("%d",&ch);
for(i=0;i<=n;i++){visited[i]=0;}
}
}
void add(int item)
{
if(rear==19)
printf("QUEUE FULL");
else
{
if(rear==-1)
{
q[++rear] = item;
front++;
}
else
q[++rear]=item;
}
}
int delete()
{
int k;
if ((front>rear)||(front==-1))
return (0);
else
{
k=q[front++];
return(k);
}
}
void push( int item )
{
if ( top == 19 )
printf( "Stack overflow " );
else
stack[ ++top ] = item;
}
int pop()
{
int k;
if ( top == -1 )
return ( 0 );
else
{
k = stack[ top-- ];
return ( k );
}
}
bfs(int s,int n)
{
int i,p;
add(s);
visited[s]=1;
p=delete();
if(p!=0) printf("%d",p);
while(p!=0)
{
for(i=1;i<=n;i++)
{
if((arr[p][i]!=0)&&(visited[i]==0))
{
add(i);
visited[i]=1;
}
}
p=delete();
if(p!=0) printf("%d",p);
}
for(i=1;i<=n;i++)
{
if(visited[i]==0) bfs(i,n);
}
}
dfs(int s,int n)
{
int k,i;
push(s);
visited[s]=1;
k=pop();
if(k!=0) printf("%d",k);
while(k!=0)
{
for(i=1;i<=n;i++)
{
if((arr[k][i]!=0)&&(visited[i]==0))
{
push(i);
visited[i]=1;
}
k=pop();
if(k!=0) printf("%d",&k);
}
}
for(i=1;i<=n;i++){
if(visited[i]==0) dfs(i,n);
}
}
Recent Comments