0
2.9kviews
Write a program in C to implement the BFS traversal of a graph. Explain the code with an example
0
91views
    BFS Traversal Program
#include<stdio.h>
#include<stdlib.h>

#define MAX 100

#define initial 1
#define waiting 2
#define visited 3

int n;
int state[MAX];
void create_graph();
void BF_Traversal();
void BFS(int v);

int queue[MAX], front = -1,rear = -1;
void insert_queue(int vertex);
int delete_queue();
int isEmpty_queue();

int main()
{
create_graph();
BF_Traversal();
return 0;
}

void BF_Traversal()
{
int v;

for(v=0; v<n; v++)
state[v] = initial;

printf("Enter Start Vertex for BFS: \n");
scanf("%d", &v);
BFS(v);
}

void BFS(int v)
{
int i;

insert_queue(v);
state[v] = waiting;

while(!isEmpty_queue())
{
v = delete_queue( );
printf("%d ",v);
state[v] = visited;

for(i=0; i<n; i++)
{
if(adj[v][i] == 1 && state[i] == initial)
{
insert_queue(i);
state[i] = waiting;
}
}
}
printf("\n");
}

void insert_queue(int vertex)
{
if(rear == MAX-1)
printf("Queue Overflow\n");
else
{
if(front == -1)
front = 0;
rear = rear+1;
queue[rear] = vertex ;
}
}

int isEmpty_queue()
{
if(front == -1 || front > rear)
return 1;
else
return 0;
}

int delete_queue()
{
int delete_item;
if(front == -1 || front > rear)
{
printf("Queue Underflow\n");
exit(1);
}

delete_item = queue[front];
front = front+1;
return delete_item;
}

void create_graph()
{
int count,max_edge,origin,destin;

printf("Enter number of vertices : ");
scanf("%d",&n);
max_edge = n*(n-1);

for(count=1; count<=max_edge; count++)
{
printf("Enter edge %d( -1 -1 to quit ) : ",count);
scanf("%d %d",&origin,&destin);

if((origin == -1) && (destin == -1))
break;

if(origin>=n || destin>=n || origin<0 || destin<0)
{
printf("Invalid edge!\n");
count--;
}
else
{
}
}
}

1. Example of BFS

a. Consider below Graph as follows

b. The vertex 0 is the starting vertex in our case. We start our traversal from the vertex 0. Then we will visit all vertices adjacent to vertex 0 i.e., 1, 4, 3. Here, we can visit these three vertices in any order.

c. Suppose we visit the vertices in order 1,3,4.The traversal would be: 0 1 3 4

d. Now, we shall visit all the vertices adjacent to 1, then all the vertices adjacent to 3 and then all the vertices adjacent to

e. So first we shall visit 2 (since it is adjacent to 1), then 6 (since it is adjacent to 3) and 5, 7 (since these are adjacent to 3.

f. The traversal would be: 0 1 3 4 2 6 5 7