Quick Expense Manger. Your free expense manager. Lots of features. The application is also ad free.

Algorithms in C - Breadth First Search

Posted on Nov. 10, 2017
algorithms-in-c-breadth-first-search

In this part of Algorithms in C tutorial series, I will explain what is Breadth First Search and I will show you - how to write a Breadth First Search from scratch in C. Breadth First Search is one of the very important Algorithms. Many programming problems are efficiently solved using Breadth First Search or BFS.

Breadth First Search is Layer by Layer traversal of a Graph. It's implemented using a Queue. Suppose S is the source node from which you would like to do the Breadth First Search.

To implement the BFS, the node S is put into a Queue. Then we run a while loop - inside the loop we check if the Queue is empty or not. If it is empty, we break the loop.

If the Queue is not empty - we remove an element from the Queue. We then check for all the unmarked neighboring nodes of the node that we have just removed and insert them into the Queue.

Let's take an example of the following Graph.


The arrows are bi-directional and that means it's an undirected Graph.

If you want to start a BFS from the source node 1 - we mark the Node 1 and insert it into a Queue. Now we run the while loop and remove the node 1 from the Queue and print it.

We then check the neighboring nodes of Node 1 which are unmarked. The nodes 2 and 4 are both unmarked. Therefore, we mark them and we insert them into the Queue.

Therefore, the Queue now contains the Nodes 2 and 4 and it's not Empty. So, the while loop continues. We now remove an element which is Node 2 from the Queue and print it.

We check for the neighboring nodes of Node 2 which are unmarked. The Node 1 is a neighboring node of Node 2 but it's already marked. So, we ignore it. Node 3 which is another neighboring node of Node 2, is unmarked. Therefore, we mark it and we insert it into the Queue.

Now we remove Node 4 from the Queue and print it. We find that all the neighboring nodes of Node 4 which are nodes 1 and 3 are already marked. Therefore, we just continue with the loop.

We now remove the Node 3 from the Queue and print it. We then mark and insert the unmarked neighboring Node 5 of node 3 into the Queue.

We now remove the only element which is Node 5 from the Queue and print it. We don't have any unmarked neighboring node of Node 5 to be inserted into the Queue. Therefore, the Algorithm ends.

Below is the complete working code for Breadth First Search Algorithms in C using Adjacency List and Queue . I have taken Nodes as integer. You can modify the code to change the data types of the Nodes as per your requirement.

#include <stdio.h>
#include <stdlib.h>
struct node{
int v;
int marked;
int layer;
struct node *next;
};
struct Graph{
int V;
int E;
struct node **adjList;
};
struct queue{
struct node *front;
struct node *rear;
};
void insertQ(struct queue *q,int v){
if(!q->front && !q->rear){
q->front = (struct node*)malloc(sizeof(struct node));
q->front->v = v;
q->front->next = NULL;
q->rear = q->front;
}
else if(q->front == q->rear){
q->rear = (struct node*)malloc(sizeof(struct node));
q->rear->v = v;
q->rear->next = NULL;
q->front->next = q->rear;
}
else{
struct node *temp = (struct node*)malloc(sizeof(struct node));
temp->v = v;
q->rear->next = temp;
q->rear = temp;
q->rear->next = NULL;
}
}
int dQ(struct queue *q){
int v;
v = q->front->v;
struct node *temp = q->front;
q->front = q->front->next;
if(!q->front)
q->rear = NULL;
free(temp);
return v;
}
struct Graph *createGraph(){
int V,E;
printf("Enter the number of Nodes in the Graph\n");
scanf("%d",&V);
printf("Enter the number of Edges in the Graph\n");
scanf("%d",&E);
struct Graph *G = (struct Graph*)malloc(sizeof(struct Graph));
G->V = V;
G->E = E;
G->adjList = (struct node**)malloc(sizeof(struct node*)*V);
int i;
for(i=0;i<V;i++){
G->adjList[i] = (struct node*)malloc(sizeof(struct node));
G->adjList[i]->v = i;
G->adjList[i]->marked = G->adjList[i]->layer = 0;
G->adjList[i]->next = NULL;
}
printf("\nNote - Node numbers should start with 0\n\n");
for(i=0;i<E;i++){
int u,v;
printf("Enter the nodes of the Edge %d\n",i+1);
scanf("%d%d",&u,&v);
struct node *temp = (struct node*)malloc(sizeof(struct node));
temp->v = v;
temp->next = G->adjList[u]->next;
G->adjList[u]->next = temp;
temp = (struct node*)malloc(sizeof(struct node));
temp->v = u;
temp->next = G->adjList[v]->next;
G->adjList[v]->next = temp;
}
return G;
}
void BFS(struct Graph *G,struct queue *q,int layer){
while(q->front){
while(q->front && (G->adjList[q->front->v]->layer == layer)){
int v = dQ(q);
printf("%d ",v);
struct node *head = G->adjList[v]->next;
while(head){
if(G->adjList[head->v]->marked){
head = head->next;
continue;
}
G->adjList[head->v]->layer = layer + 1;
G->adjList[head->v]->marked = 1;
insertQ(q,head->v);
head = head->next;
}
}
layer++;
printf("\n");
}
}
void main(){
struct Graph *G = createGraph();
struct queue *Q = (struct queue*)malloc(sizeof(struct queue));
Q->front = Q->rear = NULL;
insertQ(Q,0);
G->adjList[0]->marked = 1;
G->adjList[Q->front->v]->layer = 0;
BFS(G,Q,0);
}

If you have any doubt regarding the code or any other concept, please leave your queries in the comment section.

Sharing is Caring!

Quick Expense Manger. Your free expense manager. Lots of features. The application is also ad free.

GET FREE UPDATES


RECOMMENDED POSTS FOR YOU


profile image

Kaushik Baruah


ABOUT

My name is Kaushik Baruah and I am the chief blogger on this Blog and here I like to share my experience as software engineer and research engineer with my online readers. I will try to focus on career planning, latest emerging technologies and tutorials on various computer science subjects. You can follow me on Twitter, Facebook and Google+

GET FREE UPDATES

POPULAR POSTS

Copyright © 2016
About Us

My name is Kaushik Baruah and I am the chief blogger on this Blog and here I like to share my experience as software engineer and research engineer with my online readers. I will try to focus on career planning, latest emerging technologies and tutorials on various computer science subjects.

Get Free Updates