This is a program for the Depth First Search as well as Breadth first search. If you have any doubts, please let me know.
#include<stdio.h>
int adj[50][50];
int visited[50];
void adjcreate();
void dfs(int);
void bfs(int);
int n;
main()
{
int i, v, ch;
adjcreate();
do
{
printf("\nMENU:\n1.DFS\n2.BFS\n3.Exit\n");
printf("Enter your choice:");
scanf("%d",&ch);
switch (ch)
{
case 1:
printf("\nEnter
starting node for DFS:");
scanf("%d",&v);
for (i=1;i<=n;i++)
visited[i]=0;
dfs(v);
break;
case 2:
printf("\nEnter
starting node for BFS:");
scanf("%d",&v);
for (i=1;i<=n;i++)
visited[i]=0;
bfs(v);
break;
case 3:
break;
default:
printf("Wrong
choice!\n");
break;
}
}while(ch!=3);
}
void adjcreate()
{
int i,j,ch1;
printf("Enter the number of nodes :");
scanf("%d", &n);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf("\n Press 1 if %d is connected to %d:",i,j);
scanf("%d",&ch1);
if(ch1==1)
{
adj[i][j]=1;
}
else
{
adj[i][j]=0;
}
}
}
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
printf(" %d ",adj[i][j]);
printf("\n");
}
}
void dfs(int v)
{
int i,stack[50],top=-1,pop;
top++;
stack[top]=v;
while(top>=0)
{
pop=stack[top];
top--;
if(visited[pop]==0)
{
printf(" %d
",pop);
visited[pop]=1;
}
else
continue;
for(i=n;i>=1;i--)
{
if(adj[pop][i]==1&&visited[i]==0)
{
top++;
stack[top]=i;
}
}
}
}
void bfs(int v)
{
int i,front,rear;
int que[50];
front=rear=-1;
printf(" %d ",v);
visited[v]=1;
rear++;
front++;
que[rear]=v;
while(front<=rear)
{
v=que[front];
front++;
for (i=1;i<=n;i++)
{
if (adj[v][i]==1&&visited[i]==0)
{
printf(" %d
",i);
visited[i]=1;
rear++;
que[rear]=i;
}
}
}
}
No comments:
Post a Comment