Search Tutorials

Saturday 20 April 2013

C code to implement BFS and DFS

/* C program to implement BFS(breadth-first search) and DFS(depth-first search) algorithm */

#include<stdio.h>

int q[20],top=-1,front=-1,rear=-1,a[20][20],vis[20],stack[20];
int delete();
void add(int item);
void bfs(int s,int n);
void dfs(int s,int n);
void push(int item);
int pop();

void main()
{
int n,i,s,ch,j;
char c,dummy;
printf("ENTER THE NUMBER VERTICES ");
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 0 ",i,j);
scanf("%d",&a[i][j]);
}
}
printf("THE ADJACENCY MATRIX IS\n");
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
printf(" %d",a[i][j]);
}
printf("\n");
}

do
{
for(i=1;i<=n;i++)
vis[i]=0;
printf("\nMENU");
printf("\n1.B.F.S");
printf("\n2.D.F.S");
printf("\nENTER YOUR CHOICE");
scanf("%d",&ch);
printf("ENTER THE SOURCE VERTEX :");
scanf("%d",&s);

switch(ch)
{
case 1:bfs(s,n);
break;
case 2:
dfs(s,n);
break;
}
printf("DO U WANT TO CONTINUE(Y/N) ? ");
scanf("%c",&dummy);
scanf("%c",&c);
}while((c=='y')||(c=='Y'));
}


//**************BFS(breadth-first search) code**************//
void bfs(int s,int n)
{
int p,i;
add(s);
vis[s]=1;
p=delete();
if(p!=0)
printf(" %d",p);
while(p!=0)
{
for(i=1;i<=n;i++)
if((a[p][i]!=0)&&(vis[i]==0))
{
add(i);
vis[i]=1;
}
p=delete();
if(p!=0)
printf(" %d ",p);
}
for(i=1;i<=n;i++)
if(vis[i]==0)
bfs(i,n);
}


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);
}
}


//***************DFS(depth-first search) code******************//
void dfs(int s,int n)
{
int i,k;
push(s);
vis[s]=1;
k=pop();
if(k!=0)
printf(" %d ",k);
while(k!=0)
{
for(i=1;i<=n;i++)
if((a[k][i]!=0)&&(vis[i]==0))
{
push(i);
vis[i]=1;
}
k=pop();
if(k!=0)
printf(" %d ",k);
}
for(i=1;i<=n;i++)
if(vis[i]==0)
dfs(i,n);
}
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);
}
}

/* Output of BFS(breadth-first search) and DFS(depth-first search) program */

C code to implement BFS and DFS
Output of BFS and DFS Program

C code to implement BFS and DFS
Output of BFS and DFS Program

For more related to Data Structure check List of Data Structure Programs. If you like this program, Please share and comment to improve this blog.

14 comments:

  1. what is the roll of dummy character here..? why we have used two times scanf()..?

    ReplyDelete
    Replies
    1. Sorry, dummy character is unused. remove it..Thanks

      Delete
  2. your output is wrong.

    ReplyDelete
  3. This comment has been removed by the author.

    ReplyDelete
  4. [A code for Search any node in Graph Using BFS & Traversing any start to any end]

    #include

    int q[20],top=-1,front=-1,rear=-1,a[20][20],vis[20],stack[20],s1;

    int delete();
    void add(int item);
    void bfs(int s,int n);
    void dfs(int s,int n);
    void push(int item);
    int pop();

    void main()
    {
    int n,i,s,ch,j;
    char c,dummy;
    printf("What is the number of VERTICES : ");
    scanf("%d",&n);
    // for(i=1; i<=n; i++)
    // {
    // for(j=1; j<=n; j++)
    // {
    // printf("%d Has a node with %d (1/0) ",i,j);
    // scanf("%d",&a[i][j]);
    // }
    // }
    if(n>0)
    {

    printf("How many Edges : \n");
    int edge,sss1,sss2,chk1,chk2;
    scanf("%d",&edge);
    printf("\n***[Input Edge VERTICES. i.e. for 1 & 2 connection input 1 then 2]***");
    for(sss1=1;sss1<=edge;sss1++)
    {
    printf("\n%d. Input Edges : \n",sss1);
    scanf("%d",&chk1);
    scanf("%d",&chk2);
    a[chk1][chk2]=1;
    a[chk2][chk1]=1;
    }


    }


    printf("Adjacency Matrix :\n");
    for(i=1; i<=n; i++)
    {
    for(j=1; j<=n; j++)
    {
    printf(" %d",a[i][j]);
    }
    printf("\n");
    }

    do
    {
    for(i=1; i<=n; i++)
    vis[i]=0;
    printf("\nChoose here -");
    printf("\n1. B.F.S");
    printf("\n2. Exit");
    printf("\nEnter Your Choose : ");
    scanf("%d",&ch);
    if(ch==1)
    {
    printf("Enter the Start Node : ");
    scanf("%d",&s);
    printf("Enter the search Node : ");
    scanf("%d",&s1);
    }
    else
    break;

    switch(ch)
    {
    case 1:
    bfs(s,n);
    break;
    case 2:
    break;
    }
    printf("\nDo you want to continue(Y/N) ? ");
    scanf("%c",&dummy);
    scanf("%c",&c);
    }
    while((c=='y')||(c=='Y'));
    }



    void bfs(int s,int n)
    {
    int p,i;
    add(s);
    vis[s]=1;
    p=delete();
    if(p!=0)
    printf(" %d ",p);
    while(p!=0)
    {
    for(i=1; i<=n; i++)
    if((a[p][i]!=0)&&(vis[i]==0))
    {
    add(i);
    vis[i]=1;
    }
    p=delete();
    if(p!=0&p<=s1)
    printf(" %d ",p);
    }
    for(i=1; i<=n; i++)
    if(vis[i]==0)
    bfs(i,n);
    }


    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);
    }
    }

    ReplyDelete
  5. PROBLEM WITH DFS PART

    ReplyDelete
  6. #include
    #include
    int a[20][20],q[20],visited[20],n,i,j,f=0,r=-1;
    void bfs(int v)
    {
    for (i=1;i<=n;i++)
    {
    if(a[v][i]!=0 && visited[i]==0)
    {

    q[r++]=i;
    visited[i]=1;
    printf("%d\t",i);
    }
    }
    f=f+1;
    if(f<=r)
    bfs(q[f]);
    }
    void DFS(int i)
    {
    printf("%d\t",i);
    visited[i]=1;
    for(j=1;j<=n;j++)
    if(!visited[j]&&a[i][j]==1)
    DFS(j);
    }
    void main()
    {
    int c;
    printf("\n******MENU******\n");
    printf("\n1. BFS ON GRAPH \n2. DFS ON
    GRAPH\n3. EXIT\n");
    printf("\n Enter the number of vertices:");
    scanf("%d",&n);
    for (i=1;i<=n;i++)
    {
    q[i]=0;
    visited[i]=0;
    }
    printf("\n Enter graph data in matrix form:\n");
    for (i=1;i<=n;i++)
    for (j=1;j<=n;j++)
    scanf("%d",&a[i][j]);
    while(1)
    {
    printf("\n\nenter your choice: ");
    scanf("%d",&c);
    switch(c)
    {
    case 1:
    printf("\n BFS TRAVERSAL IS :\n");
    f=r=1;
    q[r]=1;
    visited[1]=1;
    printf("1\t");
    bfs(1);
    break;
    case 2:
    printf("\n DFS TRAVERSAL IS :\n");
    for(i=1;i<=n;i++)
    visited[i]=0;
    DFS(1);
    break;
    case 3:
    printf("\nEXITING....\n");
    exit(0);
    default: printf("enter valid
    choicE!!\n");
    }
    }

    }

    ReplyDelete
  7. Hi could you please share the algorithm of this program..

    ReplyDelete
  8. rear is not initialising to -1 ,like vis.
    .i tried with n=7, at 3rd time i got QUEUE FULL message

    i suggest to add front=rear= -1 at 86 th line

    ReplyDelete
  9. how to implement A* search in this ?

    ReplyDelete

Back to Top