/* 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 */

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.

#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 */

Output of BFS and DFS Program |

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.

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

ReplyDeleteSorry, dummy character is unused. remove it..Thanks

DeleteThanks broo

ReplyDeleteyour output is wrong.

ReplyDeleteThis comment has been removed by the author.

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

ReplyDelete#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);

}

}

this program is incorrect, it is giving the wrong output

ReplyDeleteThis comment has been removed by the author.

ReplyDeleteThis comment has been removed by the author.

ReplyDeleteThis comment has been removed by the author.

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

ReplyDeleteI 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?

ReplyDeletebusiness consultancy firms singaporeNice 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

ReplyDeleteBeginners Code Examples

ReplyDeleteI 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

ReplyDeletewhoah 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

ReplyDeleteIt'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!

ReplyDeleteaudienceHello 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

ReplyDeleteHi 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

ReplyDeleteWoah! 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

ReplyDeleteThe 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.

ReplyDeletefresh food for dogs singaporeHave 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