Key Concepts
Queue Data Structure
BFS uses a queue to keep track of the nodes to be explored next.
Visited Array
To avoid revisiting nodes, BFS maintains a list or array of visited nodes.
Levelwise Exploration
Nodes are visited level by level, ensuring complete traversal.
Process Breakdown

Initialization: The source node is marked as visited & enqueued.

Traversal: While the queue is not empty, the node at the front of the queue is dequeued & its unvisited neighbors are marked as visited & enqueued.
 Completion: The process continues until the queue is empty, indicating all reachable nodes have been visited.
BFS Program in C using Adjacency List
When implementing BFS in C, one efficient way to represent a graph is through an adjacency list. This method uses an array of lists to represent the connections between nodes. Here's a stepbystep guide on how to create a BFS program using an adjacency list:
1. Structure Definition
First, define a structure for the graph and the nodes in the list:
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int vertex;
struct node* next;
} Node;
typedef struct graph {
int numVertices;
Node** adjLists;
int* visited;
} Graph;
2. Node Creation
Create a function to create a new node:
Node* createNode(int v) {
Node* newNode = malloc(sizeof(Node));
newNode>vertex = v;
newNode>next = NULL;
return newNode;
}
3. Graph Initialization
Initialize the graph with the number of vertices and allocate memory:
Graph* createGraph(int vertices) {
Graph* graph = malloc(sizeof(Graph));
graph>numVertices = vertices;
graph>adjLists = malloc(vertices * sizeof(Node*));
graph>visited = malloc(vertices * sizeof(int));
int i;
for (i = 0; i < vertices; i++) {
graph>adjLists[i] = NULL;
graph>visited[i] = 0;
}
return graph;
}
4. Adding Edges
Add edges to the graph:
void addEdge(Graph* graph, int src, int dest) {
// Add edge from src to dest
Node* newNode = createNode(dest);
newNode>next = graph>adjLists[src];
graph>adjLists[src] = newNode;
// Add edge from dest to src for undirected graph
newNode = createNode(src);
newNode>next = graph>adjLists[dest];
graph>adjLists[dest] = newNode;
}
5. BFS Implementation
Implement the BFS algorithm using a queue:
void bfs(Graph* graph, int startVertex) {
Node* queue = createQueue();
graph>visited[startVertex] = 1;
enqueue(queue, startVertex);
while (!isEmpty(queue)) {
int currentVertex = dequeue(queue);
printf("Visited %d\n", currentVertex);
Node* temp = graph>adjLists[currentVertex];
while (temp) {
int adjVertex = temp>vertex;
if (graph>visited[adjVertex] == 0) {
graph>visited[adjVertex] = 1;
enqueue(queue, adjVertex);
}
temp = temp>next;
}
}
}
BFS Program in C using Adjacency Matrix
Another common way to implement BFS in C is by using an adjacency matrix. This approach is particularly useful for dense graphs where the matrix representation might be more spaceefficient than a list.
1. Structure Definition
Start by defining the graph structure with a matrix:
#include <stdio.h>
#include <stdlib.h>
typedef struct graph {
int numVertices;
int** adjMatrix;
int* visited;
} Graph;
2. Graph Initialization
Initialize the graph with the number of vertices:
Graph* createGraph(int vertices) {
Graph* graph = malloc(sizeof(Graph));
graph>numVertices = vertices;
graph>adjMatrix = malloc(vertices * sizeof(int*));
for (int i = 0; i < vertices; i++) {
graph>adjMatrix[i] = malloc(vertices * sizeof(int));
for (int j = 0; j < vertices; j++)
graph>adjMatrix[i][j] = 0;
}
graph>visited = malloc(vertices * sizeof(int));
for (int i = 0; i < vertices; i++)
graph>visited[i] = 0;
return graph;
}
3. Adding Edges
Function to add edges to the graph:
void addEdge(Graph* graph, int src, int dest) {
graph>adjMatrix[src][dest] = 1;
graph>adjMatrix[dest][src] = 1; // For undirected graph
}
4. BFS Implementation
Implement BFS for the adjacency matrix:
void bfs(Graph* graph, int startVertex) {
int queue[1000], front = 1, rear = 1;
graph>visited[startVertex] = 1;
queue[++rear] = startVertex;
while (front != rear) {
int currentVertex = queue[++front];
printf("Visited %d\n", currentVertex);
for (int i = 0; i < graph>numVertices; i++) {
if (graph>adjMatrix[currentVertex][i] && !graph>visited[i]) {
graph>visited[i] = 1;
queue[++rear] = i;
}
}
}
}
BFS Program in C using Queue
In this section, we'll focus on implementing the BreadthFirst Search (BFS) algorithm in C using a queue, a crucial data structure for managing the nodes during traversal.
1. Queue Implementation
First, we need to implement a queue that will be used in the BFS algorithm:
#include <stdio.h>
#include <stdlib.h>
typedef struct queue {
int items[1000];
int front;
int rear;
} Queue;
Queue* createQueue() {
Queue* q = malloc(sizeof(Queue));
q>front = 1;
q>rear = 1;
return q;
}
int isEmpty(Queue* q) {
return q>rear == 1;
}
void enqueue(Queue* q, int value) {
if (q>rear == 999)
printf("\nQueue is Full!!");
else {
if (q>front == 1)
q>front = 0;
q>rear++;
q>items[q>rear] = value;
}
}
int dequeue(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) {
q>front = q>rear = 1;
}
}
return item;
}
2. Graph Definition & Initialization
Define the graph structure & initialize it:
typedef struct graph {
int numVertices;
int** adjMatrix;
int* visited;
} Graph;
Graph* createGraph(int vertices) {
// [Graph Initialization Code from Previous Section]
}
3. BFS Implementation with Queue
Now, implement BFS using the queue:
void bfs(Graph* graph, int startVertex) {
Queue* q = createQueue();
graph>visited[startVertex] = 1;
enqueue(q, startVertex);
while (!isEmpty(q)) {
int currentVertex = dequeue(q);
printf("Visited %d\n", currentVertex);
for (int j = 0; j < graph>numVertices; j++) {
if (graph>adjMatrix[currentVertex][j] && !graph>visited[j]) {
graph>visited[j] = 1;
enqueue(q, j);
}
}
}
}
Frequently Asked Questions
What makes BFS different from DFS in terms of graph traversal?
BFS (BreadthFirst Search) explores a graph level by level, ensuring a comprehensive visit to each node's neighbors before diving deeper. In contrast, DFS (DepthFirst Search) delves deep into one path of the graph before backtracking. This fundamental difference makes BFS suitable for shortest path finding, while DFS is often used for connectivity checking.
How does BFS handle cycles in a graph?
BFS can efficiently handle cycles in a graph by keeping track of visited nodes. When a node is visited, it's marked as such, preventing the algorithm from revisiting and entering an infinite loop. This mechanism is crucial for BFS's application in realworld problems like network routing.
Can BFS be used for weighted graphs?
While BFS is primarily designed for unweighted graphs, it can be adapted for weighted graphs in specific scenarios, especially when weights are uniform or irrelevant to the task at hand. However, for general pathfinding in weighted graphs, algorithms like Dijkstra's or A* are more appropriate due to their ability to factor in edge weights.
Conclusion
BreadthFirst Search (BFS) is a fundamental algorithm in computer science, essential for students delving into graph theory and its applications. Through its implementation in C using different data structures like adjacency lists, matrices, and queues, we've explored its versatility and practical applications. This comprehensive look at BFS, equipped with code examples and explanations, aims to deepen understanding and inspire further exploration into this vital algorithm. Remember, the real power of BFS lies not just in the code, but in the logical thinking and problemsolving skills it fosters.
You can refer to our guided paths on the Coding Ninjas. You can check our course to learn more about DSA, DBMS, Competitive Programming, Python, Java, JavaScript, etc.
Also, check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc., as well as some Contests, Test Series, and Interview Experiences curated by top Industry Experts.