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.

37 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

  20. Hey there would you mind sharing which blog platform you're working with? I'm looking to start my own blog soon but I'm having a hard time selecting between BlogEngine/Wordpress/B2evolution and Drupal. The reason I ask is because your design and style seems different then most blogs and I'm looking for something unique. P.S My apologies for being off-topic but I had to ask!
    painting services Singapore

    ReplyDelete
  21. Do you mind if I quote a few of your posts as long as I provide credit and sources back to your website? My blog site is in the exact same niche as yours and my visitors would really benefit from a lot of the information you present here. Please let me know if this okay with you. Appreciate it! web design course in singapore

    ReplyDelete
  22. Wow that was strange. I just wrote an incredibly long comment but after I clicked submit my comment didn't show up. Grrrr... well I'm not writing all that over again. Anyways, just wanted to say fantastic blog! best children classes singapore

    ReplyDelete
  23. you are really a good webmaster. The site loading speed is amazing. It seems that you're doing any unique trick. Moreover, The contents are masterwork. you have done a excellent job on this topic! web e commerce

    ReplyDelete
  24. Here are some of the working methods on how to download roblox assets, including a roblox asset downloader

    ReplyDelete
  25. Playing on Xbox is very exciting, there are always some great games to play and you also have the ability to boost a gamer score https://freexboxlivecodes2019.com/

    ReplyDelete
  26. I loved as much as you will receive carried out right here. The sketch is tasteful, your authored subject matter stylish. nonetheless, you command get bought an edginess over that you wish be delivering the following. unwell unquestionably come further formerly again since exactly the same nearly very often inside case you shield this increase.
    singapore divorce lawyer free consultation

    ReplyDelete
  27. Does your site have a contact page? I'm having problems locating it but, I'd like to send you an e-mail. I've got some creative ideas for your blog you might be interested in hearing. Either way, great website and I look forward to seeing it grow over time.
    cheap brochure printing in Singapore

    ReplyDelete
  28. Wonderful blog! I found it while surfing around on Yahoo News. Do you have any suggestions on how to get listed in Yahoo News? I've been trying for a while but I never seem to get there! Thanks
    car insurance

    ReplyDelete
  29. Xbox Live code generator or Xbox Live Gold Membership codes generator is online web-based tool which generates free xbox codes Xbox live codes

    ReplyDelete
  30. Very very nice post.
    Win for free Xbox codes live visit here:
    http://freexboxcodeslive.com

    ReplyDelete
  31. I'm not sure exactly why but this site is loading extremely slow for me. Is anyone else having this issue or is it a issue on my end? I'll check back later and see if the problem still exists.
    evergreen SEO strategies

    ReplyDelete
  32. Wow that was strange. I just wrote an very long comment but after I clicked submit my comment didn't appear. Grrrr... well I'm not writing all that over again. Regardless, just wanted to say excellent blog! web usability testing

    ReplyDelete
  33. Hi there! This is my first visit to your blog! We are a collection of volunteers and starting a new initiative in a community in the same niche. Your blog provided us valuable information to work on. You have done a outstanding job!
    design a mobile-friendly website

    ReplyDelete

Back to Top