Wednesday 22 June 2016

BFS AND DFS

BFS & DFS
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>
int stack[100],top=-1,f=0,r=0,que[100];
void push(int k)
{
stack[++top]=k;

}
int pop()
{
int j=stack[top];
top--;
return j;
}
void enq(int k1)
{
que[r++]=k1;
}
int deq()
{
int j1=que[f++];
return j1;
}

int main()
{

int t,n,src,des,source;
scanf("%d%d",&t,&n);

int adj[100][100]={0};
for(int i=1;i<=n;i++)
{
scanf("%d%d",&src,&des);
adj[src][des]=adj[des][src]=1;
}
scanf("%d",&source);
int known[100]={0},v=0;
push(source);
while(top>=0)
{
int u=pop();
if(v!=t){
printf("%d ",u);
v++;
}
known[u]=1;
for(int i=1;i<=t;i++)
{
if(adj[u][i]!=0&&known[i]!=1)
push(i);
}
}
printf("\n");
int known1[100] ={0};
enq(source);
while(r>f)
{
int u1=deq();
known1[u1]=1;
printf("%d ",u1);
for(int i=1;i<=t;i++)
{
if(adj[u1][i]!=0&&known1[i]!=1){
known1[i]=1;
enq(i);
}
}
}
return 0;
}

No comments:

Post a Comment