Data Structure and Algorithm
Breadth First Search  BFS Algorithm with Practical Examples
 Breadth First Search
 BFS Algorithm
 Working Principle of BFS
 Implementation of BFS in C and C++
 Time Complexity of BFS
 Space Complexity of BFS
 Applications of BFS
 Run C Programming Online Compiler
Imagine a wildfire igniting in a vast, densely wooded forest. The fire starts at one point and spreads to adjacent areas. Fire moves to new areas directly adjacent to those already burning, creating a wave that moves outward from the origin. This spreading pattern mirrors the characteristics of the BFS
algorithm, moving uniformly to all directly adjacent areas in successive waves.
BreadthFirst Search (BFS
) is commonly used in various tasks such as routing in networks, navigating social networks, crawling web pages, guiding GPS navigation, solving puzzles, and managing memory in programming through garbage collection.
¶Breadth First Search
Breadth First Search (BFS
) is a fundamental traversing algorithm in graph theory. It begins at a specific node and explores all neighboring nodes at the current level before moving on to nodes at the next level. Numerous graph algorithms heavily rely on BFS
. For instance, searching for the shortest path from one node to another in a graph often utilizes BFS
. This algorithm systematically explores neighboring nodes, making it particularly efficient for finding optimal paths.
¶BFS Algorithm
BreadthFirst Search (BFS
) begins at a chosen vertex and explores neighboring vertices iteratively in a levelbylevel manner. Here’s a basic outline of the BFS algorithm:
 Choose a starting vertex and mark it as visited.
 Enqueue the starting vertex into a queue data structure.
 While the queue is not empty,
 Dequeue a vertex from the front of the queue.
 Visit the dequeued vertex and explore its adjacent vertices.
 For each unvisited adjacent vertex, mark it as visited and enqueue it into the queue.
 Repeat step 3 until all reachable vertices are visited or the queue becomes empty.
 If all reachable vertices are visited, terminate the algorithm. Otherwise, continue exploring vertices by dequeuing from the queue.
¶Working Principle of BFS
Let’s see working principle of BFS
for the following graph,

Initialization:
 Start at the node 1.
 Create a queue to help manage the nodes to be explored and initialize it with the start node, in this case,
queue = [1]
.  Mark node 1 as visited to avoid revisiting it
visited = {1}
.

Exploration:
 Dequeue an element from the front of the queue. Here, we start with node 1.
current_node = 1
.  Examine each adjacent node of node 1. According to the graph, these are nodes 2 and 3.
 Dequeue an element from the front of the queue. Here, we start with node 1.

Checking and Enqueuing Neighbors of Node 1:
 For each adjacent node:
 If it has not been visited, mark it as visited and enqueue it.
 Process node 2: Mark as visited (
visited = {1, 2}
) and enqueue (queue = [2]
).  Process node 3: Mark as visited (
visited = {1, 2, 3}
) and enqueue (queue = [2, 3]
).
 For each adjacent node:

Continuing with Node 2:
 Dequeue node 2.
current_node = 2
.  Examine its neighbors (nodes 6 and 4).
 Node 6: Mark as visited (
visited = {1, 2, 3, 6}
) and enqueue (queue = [3, 6]
).  Node 4: Mark as visited (
visited = {1, 2, 3, 6, 4}
) and enqueue (queue = [3, 6, 4]
).
 Node 6: Mark as visited (
 Dequeue node 2.

Continuing with Node 3:
 Dequeue node 3.
current_node = 3
.  Examine its neighbors (nodes 4 and 5).
 Node 4 is already visited, so ignore.
 Node 5: Mark as visited (
visited = {1, 2, 3, 6, 4, 5}
) and enqueue (queue = [6, 4, 5]
).
 Dequeue node 3.

Finishing Up:
 Continue the process until the queue is empty, dequeuing nodes 6, 4, and 5 sequentially, each time checking their neighbors. Since all neighbors will have been already visited by the time we process these nodes, no new nodes are added to the queue.
 Once the queue is empty, the BFS traversal is complete.
The final order of traversal in BFS starting from node 1 in this graph will be: 1, 2, 3, 6, 4, 5. This order reflects how BFS explores all neighbors at the current depth before moving to nodes at the next depth level.
¶Implementation of BFS in C and C++
Here is the C
implementation of BFS
#include <stdio.h>
#include <stdbool.h>
#define MAX_VERTICES 100
int graph[MAX_VERTICES][MAX_VERTICES];
bool visited[MAX_VERTICES];
int queue[MAX_VERTICES];
int front = 1, rear = 1;
void enqueue(int vertex) { queue[++rear] = vertex; }
int dequeue() { return queue[++front]; }
bool isEmpty() { return front == rear; }
void addEdge(int u, int v) {
graph[u][v] = 1;
graph[v][u] = 1; // Since the graph is undirected
}
void BFS(int startVertex, int numVertices) {
visited[startVertex] = true;
enqueue(startVertex);
while (!isEmpty()) {
int currentVertex = dequeue();
printf("%d ", currentVertex);
for (int i = 1; i <= numVertices; i++) {
if (graph[currentVertex][i] && !visited[i]) {
visited[i] = true;
enqueue(i);
}
}
}
}
int main() {
int numVertices = 6;
// Initialize graph (adjacency matrix) and visited array
for (int i = 0; i < MAX_VERTICES; i++) {
for (int j = 0; j < MAX_VERTICES; j++) {
graph[i][j] = 0;
}
visited[i] = false;
}
// Adding edges as per your graph
addEdge(1, 2);
addEdge(1, 3);
addEdge(2, 6);
addEdge(2, 4);
addEdge(3, 4);
addEdge(3, 5);
printf("BFS starting from vertex 1:\n");
BFS(1, numVertices);
return 0;
}
Here is the C++
implementation of BFS
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
// Function to add an edge to the graph (undirected graph)
void addEdge(vector<int> adj[], int u, int v) {
adj[u].push_back(v);
adj[v].push_back(u); // Since the graph is undirected
}
// Function to perform BFS on the graph
void BFS(vector<int> adj[], int startVertex, int numVertices) {
vector<bool> visited(numVertices + 1, false); // +1 for 1based index
queue<int> queue;
// Start from the given starting vertex
visited[startVertex] = true;
queue.push(startVertex);
while (!queue.empty()) {
int vertex = queue.front();
queue.pop();
cout << vertex << " ";
// Visit all the adjacent vertices
for (int adjVertex : adj[vertex]) {
if (!visited[adjVertex]) {
visited[adjVertex] = true;
queue.push(adjVertex);
}
}
}
cout << endl;
}
int main() {
int numVertices = 6; // 6 vertices labeled from 1 to 6
vector<int> adj[numVertices + 1]; // +1 for 1based index
// Adding edges as per your graph
addEdge(adj, 1, 2);
addEdge(adj, 1, 3);
addEdge(adj, 2, 6);
addEdge(adj, 2, 4);
addEdge(adj, 3, 4);
addEdge(adj, 3, 5);
cout << "Breadth First Search starting from vertex 1:" << endl;
BFS(adj, 1, numVertices);
return 0;
}
Breadth First Search starting from vertex 1:
1 2 3 6 4 5
¶Time Complexity of BFS
The time complexity of BFS
algorithm is O(V + E)
, where V
is the number of nodes and E
is the number of edges.
¶Space Complexity of BFS
The space complexity of BFS
is O(∣V∣)
, where ∣V∣
represents the number of vertices in the graph.
¶Applications of BFS
Here are a few reallife applications of BFS
:

Routing in Networks: BFS is used to find the shortest path in network routing to ensure data packets are sent via the shortest possible routes, minimizing latency and maximizing efficiency.

Navigating Social Networks: In social networks, BFS helps to explore user connections level by level, allowing features like finding friends of friends or suggesting new friends based on shortest connection paths.

Crawling Web Pages: Search engines use BFS to systematically visit web pages by starting at a source page and visiting all linked pages before moving to links that are two hops away, ensuring a thorough and orderly exploration of the web.

Guiding GPS Navigation: BFS is applied in GPS systems to compute the shortest path from one location to another by exploring all possible routes systematically, starting from the nearest and expanding outward.

Solving Puzzles: BFS is effective for solving puzzles like the sliding tile puzzle or the Rubik’s Cube by exploring all possible states from the initial configuration to find the solution that requires the fewest moves.

Managing Memory in Programming through Garbage Collection: In garbage collection, BFS can be used to identify all reachable objects in memory so that unreachable objects can be cleared, ensuring efficient memory use and preventing memory leaks.
Each application utilizes the structured, layerbylayer exploration characteristic of BFS to achieve efficient and optimal solutions in their respective fields.
¶Run C Programming Online Compiler
To make your learning more effective, exercise the coding examples in the text editor below.
Introduction to Graph Data Structure with Practical Examples
SingleSource Shortest Paths Algorithm  Dijkstra's Algorithm
All Tutorials in this playlist
Popular Tutorials
Categories

Artificial Intelligence (AI)
11

Bash Scripting
1

Bootstrap CSS
0

C Programming
14

C#
0

ChatGPT
1

Code Editor
2

Computer Engineering
3

CSS
28

Data Structure and Algorithm
18

Design Pattern in PHP
2

Design Patterns  Clean Code
1

EBook
1

Git Commands
1

HTML
19

Interview Prepration
2

Java Programming
0

JavaScript
12

Laravel PHP Framework
37

Mysql
1

Node JS
1

Online Business
0

PHP
28

Programming
8

Python
12

React Js
19

React Native
1

Redux
2

Rust Programming
15

Tailwind CSS
1

Typescript
10

Uncategorized
0

Vue JS
1

Windows Operating system
1

Woocommerce
1

WordPress Development
2
Tags
 Artificial Intelligence (AI)
 Bash Scripting
 Business
 C
 C Programming
 Csharp programming
 C++
 Code Editor
 Computer Engineering
 CSS
 Data Structure and Algorithm
 Database
 Design pattern
 Express JS
 git
 Git Commands
 github
 HTML
 Java
 JavaScript
 Laravel
 Mathematics
 MongoDB
 Mysql
 Node JS
 PHP
 Programming
 Python
 React Js
 Redux
 Rust Programming Language
 TypeScript
 Vue JS
 Windows terminal
 Woocommerce
 WordPress
 WordPress Plugin Development