Program for Breadth First Search of Graph | Amazon

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

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.

[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]

Breadth first search

 

 

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

 

Sree Hari Sanjeev

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

Leave a Reply

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