Breadth-First Search (BFS) Program in C

In this instructional exercise, we will talk about Breadth-First Search or BFS program in C with calculation and a model. Before hopping to genuine coding lets talk about something about Graph and BFS.

A Graph G = (V, E) is an accumulation of sets V and E where V is a gathering of vertices and E is a gathering of edges.

A Graph can be of two kinds:

Coordinated Graph

Undirected Graph

In information structures, there is a prevalent term known as ‘Traversal’. It is the procedure of methodicallly visiting or looking at (might be to refresh the Graph hubs) every hub in a tree information structure, precisely once.

There are two most basic techniques to navigate a Graph:

Expansiveness First Search

Profundity First Search

In this instructional exercise, we are going to concentrate on the Breadth-First Search procedure.

In this procedure, we first visit the vertex and afterward visit all the vertices adjoining the beginning vertex i.e., 0. Next, we pick the neighboring vertices in a steady progression and visit their contiguous vertices and this procedure continues forever until we arrive at the last vertex.

Broadness First Search (BFS) Example

Consider underneath Graph for instance.

The vertex 0 is the beginning vertex for our situation. We start our traversal from the vertex 0. At that point we will visit all vertices neighboring vertex 0 i.e., 1, 4, 3. Here, we can visit these three vertices in any request. Assume we visit the vertices all together 1,3,4.

The traversal would be: 0 1 3 4

Presently, we will visit all the vertices nearby 1, at that point all the vertices neighbouring 3 and afterwards all the vertices adjoining 4. So first we will visit 2 (since it is contiguous 1), at that point 6 (since it is adjoining 3) and 5, 7 (since these are neighbouring 4).

Note: Vertex 4 is adjoining vertices 1 and 3, however, it has just been visited so we’ve overlooked it.

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

Presently, we will visit all the vertices contiguous 2, 6, 5, and 7 individually. We can see that vertex 5 is adjoining vertex 2. Since it has just been navigated upon previously, we have don’t have to cross through it again and proceed onward to the following vertex.

Presently, the vertices 4 and 7 are adjoining the vertex 6. Since they have been navigated upon previously, we won’t cross on them once more. Vertex 5 doesn’t have any contiguous vertices.

Vertices 5 and 8 are neighbouring vertex 7. Since vertex 5 has been navigated upon previously, we won’t cross it once more. Be that as it may, vertex 8 has not yet been visited. So we will navigate on vertex 8.

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

Presently, we have to visit vertices neighbouring vertex 8. Notwithstanding, there is no vertex adjoining vertex 8 and consequently, we should stop the traversal here.

Note: There’s no special traversal and it very well may be diverse depending on the request for the successors.

We will take a gander at a BFS program in C for coordinated Graph utilizing a Queue. This program arrives at just those vertices that are reachable from the beginning vertex.

Broadness First Search (BFS) Program in C

#include<stdio.h>
#include<stdlib.h>
 
#define MAX 100  
 
#define initial 1
#define waiting 2
#define visited 3
 
int n;    
int adj[MAX][MAX];
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
		{
			adj[origin][destin] = 1;
		}
	}
}

Output

In the event that you discover anything off base or have any questions in regards to above Breadth-First Search (BFS) program in C at that point remark underneath.