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.

22 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
  6. This comment has been removed by the author.

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

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

    ReplyDelete
  9. when we was developing our referral program (https://www.linksmanagement.com/earn/ ) we also used these codes.

    ReplyDelete
  10. I carry on listening to the reports lecture about receiving boundless online grant applications so I have been looking around for the finest site to get one. Could you advise me please, where could i acquire some? business consultancy firms singapore

    ReplyDelete
  11. Nice blog here! Also your website loads up fast! What host are you using? Can I get your affiliate link to your host? I wish my website loaded up as fast as yours lol. van singapore

    ReplyDelete
  12. I do not even know how I ended up here, but I thought this post was good. I do not know who you are but definitely you are going to a famous blogger if you are not already ;) Cheers! spine specialist singapore

    ReplyDelete
  13. whoah this blog is magnificent i really like studying your articles. Stay up the great work! You realize, a lot of individuals are looking around for this info, you can help them greatly.outdoor led signs

    ReplyDelete
  14. It's a pity you don't have a donate button! I'd certainly donate to this outstanding blog! I suppose for now i'll settle for bookmarking and adding your RSS feed to my Google account. I look forward to brand new updates and will share this website with my Facebook group. Talk soon! audience

    ReplyDelete
  15. Hello there! I know this is kind of off topic but I was wondering if you knew where I could get a captcha plugin for my comment form? I'm using the same blog platform as yours and I'm having problems finding one? Thanks a lot! organic vegetables in chennai

    ReplyDelete
  16. Hi there, You have done an incredible job. I will definitely digg it and personally suggest to my friends. I am confident they'll be benefited from this website.Candid wedding photographers in Chennai

    ReplyDelete
  17. Woah! I'm really digging the template/theme of this blog. It's simple, yet effective. A lot of times it's very difficult to get that "perfect balance" between user friendliness and visual appearance. I must say that you've done a awesome job with this. Also, the blog loads super fast for me on Firefox. Excellent Blog! JC maths tuition

    ReplyDelete
  18. The core of your writing while sounding reasonable initially, did not settle properly with me after some time. Somewhere throughout the paragraphs you were able to make me a believer but only for a short while. I nevertheless have a problem with your leaps in logic and one would do well to fill in those breaks. When you actually can accomplish that, I will definitely end up being amazed.fresh food for dogs singapore

    ReplyDelete
  19. Have you ever considered about adding a little bit more than just your articles? I mean, what you say is valuable and all. But think about if you added some great pictures or video clips to give your posts more, "pop"! Your content is excellent but with pics and clips, this site could undeniably be one of the most beneficial in its niche. Terrific blog! coding for kids

    ReplyDelete

Back to Top