# Program for Breadth First Search of Graph | Amazon

### Question

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

Pre-requisite:

Queue DataStructure

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

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;
}
```

### Sree Hari Sanjeev

The founder of Wisdom Overflow. Software Developer at Zoho Corporation.