C program for bfs (breadth first search)

C program for bfs (breadth first search) using array. BFS is Breadth first Search, which is used to traverse unwieghted Graph. There are two most popular graph traversing technique, i.e DFS and BFS. DFs make use of Stack while, BFS make use data structure Queue. Also see c program to implement DFS.

C program for bfs (breadth first search)

#include<stdio.h>
#include<conio.h>

char que[20];
int front=0, rear=0, n;
char arr[20];
int bfs(int );
char ajMat[20][20];
char b[20];
void display();
int p=0;

int main()
{
    char v;
    printf("Enter the number of nodes in a graph");
    scanf("%d",&n);
    printf("Enter the value of node of graph"); 
    for(int i=0; i<n; i++)
    {
        scanf("%s",&b[i]);
    }

    printf("Enter the value in adjancency matrix in from of 'y' or 'n'\n");
    printf("If there exits an edge between two vertices than 'y' otherwise 'n'\n");
    for(int i=0; i<n; i++)
    printf(" %c ",b[i]);
    for(int i=0;i<n; i++)
    {
        printf("\n%c ",b[i]);
        for(int j=0; j<n; j++)
        {
             printf("%c ",v=getch());
             ajMat[i][j]=v;
        }
        printf("\n\n");
    }
    for(int i=0;i<n;i++)
    bfs(i);

    display();
    getch();
}

void display()
{
     printf("BFS of Graph : ");
     for(int i=0; i<n; i++)
     printf("%c ",arr[i]);
}

void insert(char val)
{
    que[front]=val; 
    front++;
}

char del()
{
    rear=rear+1;
    return que[rear-1];
}

bool unVisit(char val)
{
    for(int i=0; i<front; i++)
    {
         if(val==que[i])
         return false;
    }
return true;
}

int bfs(int i)
{
     char m;
     if(front==0)
     {
         insert(b[i]);
     }
     for(int j=0; j<n; j++) 
     {
         if(ajMat[i][j]=='y')
         {
              if(unVisit(b[j]))
              {
                   insert(b[j]);
              }
         }
     } 
     m=del();
     arr[p]=m;
     p++;
     return 0;
}

Here is the graph for below c program for bfs output :

c program for bfs
c program for bfs graph

Output of C program for bfs:

c program for bfs
c program for bfs

2 thoughts on “C program for bfs (breadth first search)”

  1. Great work by you my bro.. awesome. I offered same thing but used a different language.. here is code for BFS in C++ if anyone’s interested.

  2. #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] && !visited[i])
    q[++r]=i;
    if(f<=r)
    {
    visited[q[f]]=1;
    bfs(q[f++]);
    }
    }
    void main()
    {
    int v;
    clrscr();
    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]);
    printf("\n Enter the starting vertex:");
    scanf("%d",&v);
    bfs(v);
    printf("\n The node which are reachable are:\n");
    for(i=1;i<=n;i++)
    if(visited[i])
    printf("%d\t",i);
    else
    printf("\n Bfs is not possible");
    getch();
    }

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>