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:
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
- Get n from the user and dynamically create an n*n adjacency matrix to store the edges.
- Get the set of edges from the user.
- Create Visited array to check whether the node is visited or not.
- Get the starting node from the user.
- Now, Implement the Breadth First Search algorithm.
[code lang=”c”]
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.
[/code]
Program
[code lang=”c”]
#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;
}
[/code]
Suggested Reading…
C program to find Height of Binary Tree | Amazon
Print the Maximum possible K digit number