Search Tutorials

Loading...

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.

7 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. this program is incorrect, it is giving the wrong output

    ReplyDelete

Back to Top