Program for Breadth First Search of Graph | Amazon

Question

Write a program for breadth first search. Given n vertex and set of edges, task is to do breadth first traversal of the graph.

Pre-requisite:

Queue DataStructure

Breadth First Search Algorithm

Graph Representation

The most commonly used representation for graphs is adjacency matrices and adjacency lists. The adjacency matrix n*n where n is the number of vertices in the graph with the property that a[i][j] = 1 if edge(i, j) is present between i and j and a[i][j] = 0 if there is no such edge.

Logic

1. Get n from the user and dynamically create an n*n adjacency matrix to store the edges.
2. Get the set of edges from the user.
3. Create Visited array to check whether the node is visited or not.
4. Get the starting node from the user.
5.  Now, Implement the Breadth First Search algorithm.

 let Q be queue.
      Q.enqueue( s ) //Inserting s in queue

      mark s as visited.
      while ( Q is not empty)
           //Removing that vertex from queue,whose neighbour will be visited now
           v  =  Q.dequeue( )

          //processing all the neighbours of v  
          for all neighbours w of v in Graph G
               if w is not visited 
                        Q.enqueue( w )             //add w in queue
                        mark w as visited.

Program

#include<stdio.h>
#define Max 10
int q[Max];             //queue
int front=-1,rear=-1;
int main()
{
    int i,n,j;
    printf("Enter the number of vertices");
    scanf("%d",&n);
    int *arr[n];
    int visited[Max] ={0};                      //intitalizing with 0
    /*Dynamically create n*n matrix*/
    for(i = 0; i<n; i++)
        arr[i] = (int*)malloc(n*sizeof(int));

    for(i=0;i<n;i++)
        for(j=0; j<n; j++)
            arr[i][j] = 0;

    printf("Enter the edges...-1 -1 to exit\nsrc des\n");
    do{
        scanf("%d %d",&i,&j);
        if(i==-1 && j==-1)
            break;
        arr[i][j] = 1;                          //edge(i,j) where i and j are adjacent
    }while(1);

    /*Printing adjacency matrices*/
    for(i=0;i<n;i++)
        {
           for(j=0; j<n; j++)
            printf("%d",arr[i][j]);
            printf("\n");
        }

    printf("Enter the starting from node");
    scanf("%d",&i);

    /*Breath first Traversal*/
    push(i);                                    //push to the queue
    visited[i] = 1;                             //mark node 'i' as visited
    printf("%d\n",i);                           //print node 'i'

    /*Repeat until queue becomes empty*/
    while(!isQueueEmpty())
    {
        i = deque();
        printf("%d ",i);

        for(j=0; j<n; j++)
        {
            if(arr[i][j] == 1 &&!visited[j])
                {
                    push(j);
                    printf("%d ",j);            //print node 'j'
                    visited[j] = 1;
                }
        }
    }
}
void push(int vertex)
{
    if(front == -1)         //queue is empty
        {
            front = 0;
            rear = 0;
        }

    q[rear] = vertex;       //store value in queue
    rear++;                 //move rear forward
}
int deque()
{
    int data;
    if(rear==-1)
       {
         printf("Queue is empty");
         return -1;
       }

    data = q[front];                //Get data from front position

    front++;                        //move front forward
    if(front == rear)               //queue is empty
    {
        front = -1;
        rear = -1;
    }
    return data;
}
int isQueueEmpty()
{
    if(front == -1)
        return 1;
    else
        return 0;
}

Suggested Reading…

C program to find Height of Binary Tree | Amazon

Print the Maximum possible K digit number