# C Program for BFS Algorithm

Share

BFS is an algorithm for traversing or searching tree or graph data structures. It starts at the tree root and explores all of the neighbor nodes at the present depth prior to moving on to the nodes at the next depth level. The aim of the BFS algorithm is to traverse the graph as close as possible to the root node. The queue is used in the implementation of the breadth-first search.

Consider a tree

In C programming, we can implement it in two ways:

1. Using Matrix
2. Using Linked List

``````// BFS algorithm in C

#include <stdio.h>
#include <stdlib.h>
#define SIZE 40

struct queue {
int items[SIZE];
int front;
int rear;
};

struct queue* createQueue();
void enqueue(struct queue* q, int);
int dequeue(struct queue* q);
void display(struct queue* q);
int isEmpty(struct queue* q);
void printQueue(struct queue* q);

struct node {
int vertex;
struct node* next;
};

struct node* createNode(int);

struct Graph {
int numVertices;
int* visited;
};

// BFS algorithm
void bfs(struct Graph* graph, int startVertex) {
struct queue* q = createQueue();

graph->visited[startVertex] = 1;
enqueue(q, startVertex);

while (!isEmpty(q)) {
printQueue(q);
int currentVertex = dequeue(q);
printf("\n Visited %d\n", currentVertex);
struct node* temp = graph->adjLists[currentVertex];
while (temp) {
int adjVertex = temp->vertex;
if (graph->visited[adjVertex] == 0) {
}
temp = temp->next;
}
}
}

// Creating a node
struct node* createNode(int v) {
struct node* newNode = malloc(sizeof(struct node));
newNode->vertex = v;
newNode->next = NULL;
return newNode;
}

// Creating a graph
// @dev
// params no of vertices
struct Graph* createGraph(int vertices) {
struct Graph* graph = malloc(sizeof(struct Graph));
graph->numVertices = vertices;

graph->adjLists = malloc(vertices * sizeof(struct node*));
graph->visited = malloc(vertices * sizeof(int));

int i;

// initalise all node with NULL value
for (i = 0; i < vertices; i++) {
graph->visited[i] = 0;
}

return graph;
}

void addEdge(struct Graph* graph, int src, int dest) {
// Add edge from src to dest
struct node* newNode = createNode(dest);

// Add edge from dest to src
newNode = createNode(src);
}

// Create a queue
struct queue* createQueue() {
struct queue* q = malloc(sizeof(struct queue));
q->front = -1;
q->rear = -1;
return q;
}

// Check if the queue is empty
int isEmpty(struct queue* q) {
if (q->rear == -1)
return 1;
else
return 0;
}

// Adding elements into queue
void enqueue(struct queue* q, int value) {
if (q->rear == SIZE - 1)
printf("\nQueue is Full!!");
else {
if (q->front == -1)
q->front = 0;
q->rear++;
q->items[q->rear] = value;
}
}

// Removing elements from queue
int dequeue(struct queue* q) {
int item;
if (isEmpty(q)) {
printf("Queue is empty");
item = -1;
} else {
item = q->items[q->front];
q->front++;
if (q->front > q->rear) {
printf("Resetting queue ");
q->front = q->rear = -1;
}
}
return item;
}

// Print the queue
void printQueue(struct queue* q) {
int i = q->front;

if (isEmpty(q)) {
printf("Queue is empty");
} else {
printf("\nQueue contains: ");
for (i = q->front; i < q->rear + 1; i++) {
printf("%d ", q->items[i]);
}
}
}

int main() {
struct Graph* graph = createGraph(7);

bfs(graph, 0);

return 0;
}``````

OUTPUT

The equivalent matrix is:

C Program

``````#include<stdio.h>
#include<stdlib.h>
int a,q,visited,n,i,j,f=0,r=-1;
void bfs(int v) {
for (i=1;i<=n;i++)
if(a[v][i] && !visited[i])
q[++r]=i;
if(f<=r) {
visited[q[f]]=1;
bfs(q[f++]);
}
}
void main() {
int v;
printf("\n Enter the number of vertices:");
scanf("%d",&n);
for (i=1;i<=n;i++) {
q[i]=0;
visited[i]=0;
}
printf("\n Enter graph data in matrix form:\n");
for (i=1;i<=n;i++)
for (j=1;j<=n;j++)
scanf("%d",&a[i][j]);
printf("\n Enter the starting vertex:");
scanf("%d",&v);
bfs(v);
printf("\n The node which are reachable are:\n");
for (i=1;i<=n;i++)
if(visited[i])
printf("%d\t",i); else
printf("\n Bfs is not possible");

}``````

Github Repo: https://github.com/CodewithSudeep/Searching-Algo

Tree Traversal: Tree traversal techniques in DSA

Share Healing