C Program to implement BFS Algorithm for Connected Graph

By | 20.05.2017

BFS Algorithm for Connected Graph


Write a C Program to implement BFS Algorithm for Connected Graph. Here’s simple Program for traversing a directed graph through Breadth First Search(BFS),  visiting only those vertices that are reachable from start vertex.


Breadth First Search (BFS)


BFS is a traversing algorithm where you should start traversing from a selected node (source or starting node) and traverse the graph layerwise thus exploring the neighbour nodes (nodes which are directly connected to source node). You must then move towards the next-level neighbour nodes.

It employs the following rules :

  • Rule 1 − Visit the adjacent unvisited vertex. Mark it as visited. Display it. Insert it in a queue.
  • Rule 2 − If no adjacent vertex is found, remove the first vertex from the queue.
  • Rule 3 − Repeat Rule 1 and Rule 2 until the queue is empty.

Also Read : : C Program for Creation of Adjacency Matrix

Below is the source code for C Program to implement BFS Algorithm for Connected Graph which is successfully compiled and run on Windows System to produce desired output as shown below :


SOURCE CODE : :


/* C Program to implement BFS Algorithm for Connected Graph */

#include<stdio.h>
#include<stdlib.h>

#define MAX 100

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

int n; /*Number of vertices in the graph*/
int adj[MAX][MAX]; /*Adjacency Matrix*/
int state[MAX]; /*can be initial, waiting or visited*/

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;

}/*End of main()*/

void BF_Traversal()
{
 int v;

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

 printf("\nEnter starting vertex for Breadth First Search : ");
 scanf("%d", &v);
 BFS(v);
}/*End of BF_Traversal()*/

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++)
 {
 /*Check for adjacent unvisited vertices */
 if(adj[v][i] == 1 && state[i] == initial)
 {
 insert_queue(i);
 state[i] = waiting;
 }
 }
 }
 printf("\n");
}/*End of BFS()*/

void insert_queue(int vertex)
{
 if(rear == MAX-1)
 printf("\nQueue Overflow\n");
 else
 {
 if(front == -1) /*If queue is initially empty */
 front = 0;
 rear = rear+1;
 queue[rear] = vertex ;
 }
}/*End of insert_queue()*/

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

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

 del_item = queue[front];
 front = front+1;
 return del_item;
}/*End of delete_queue() */

void create_graph()
{
 int i,max_edges,origin,destin;

 printf("\nEnter number of vertices : ");
 scanf("%d",&n);
 max_edges = n*(n-1);

 for(i=1; i<=max_edges; i++)
 {
 printf("\nEnter edge %d( -1 -1 to quit ) : ",i);
 scanf("%d %d",&origin,&destin);

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

 if(origin>=n || destin>=n || origin<0 || destin<0)
 {
 printf("\nInvalid edge!\n");
 i--;
 }
 else
 {
 adj[origin][destin] = 1;
 }
 }/*End of for*/
}/*End of create_graph()*/

OUTPUT : :


/* C Program to implement BFS Algorithm for Connected Graph */

Enter number of vertices : 5

Enter edge 1( -1 -1 to quit ) : 0 1

Enter edge 2( -1 -1 to quit ) : 0 2

Enter edge 3( -1 -1 to quit ) : 0 3

Enter edge 4( -1 -1 to quit ) : 1 3

Enter edge 5( -1 -1 to quit ) : 3 2

Enter edge 6( -1 -1 to quit ) : 4 4

Enter edge 7( -1 -1 to quit ) : -1 -1

Enter starting vertex for Breadth First Search : 0
0 1 2 3

Process returned 0

If you found any error or any queries related to the above program or any questions or reviews , you wanna to ask from us ,you may Contact Us through our contact Page or you can also comment below in the comment section.We will try our best to reach up to you in short interval.


Thanks for reading the post…


Recommended Posts : :

0 0 votes
Article Rating
Subscribe
Notify of
guest
0 Comments
Oldest
Newest Most Voted
Inline Feedbacks
View all comments