C++ Program to Implement Breadth-First Search (BFS)
By Coder Scratchpad on in C/C++
Graph traversal is a cornerstone concept in computer science, used to explore all nodes of a graph systematically. Breadth-First Search (BFS) is one of the most popular graph traversal algorithms. Unlike Depth-First Search, which dives deep into one path, BFS explores all neighbors of a node level by level. This makes BFS particularly useful for finding the shortest path in unweighted graphs, detecting connected components, and exploring networks systematically.
BFS is widely applied in social network analysis, web crawling, and routing algorithms. Learning BFS in C++ not only strengthens your understanding of queues and graph representations, but also provides a foundation for more advanced algorithms like Dijkstra’s algorithm and Ford-Fulkerson. Its iterative nature and clear logic make it very approachable for beginners, while still being powerful enough to solve real-world problems efficiently.
Table of Contents
Toggle- Program 1: BFS Using Queue on an Undirected Graph
- Program 2: BFS on a Directed Graph
- Program 3: BFS to Find Shortest Path in an Unweighted Graph
- Program 4: BFS to Count Connected Components
- Frequently Asked Questions (FAQ)
- Conclusion
Program 1: BFS Using Queue on an Undirected Graph
This program demonstrates the classic BFS using a queue and a predefined undirected graph.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
void bfs(int start, vector<vector<int>> &adj) {
vector<bool> visited(adj.size(), false);
queue<int> q;
visited[start] = true;
q.push(start);
while (!q.empty()) {
int node = q.front();
q.pop();
cout << node << " ";
for (int neighbor : adj[node]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
q.push(neighbor);
}
}
}
}
int main() {
int nodes = 5;
vector<vector<int>> adj(nodes);
adj[0] = {1, 2};
adj[1] = {0, 3, 4};
adj[2] = {0};
adj[3] = {1};
adj[4] = {1};
cout << "BFS Traversal starting from node 0: ";
bfs(0, adj);
cout << endl;
return 0;
}
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
void bfs(int start, vector<vector<int>> &adj) {
vector visited(adj.size(), false);
queue q;
visited[start] = true;
q.push(start);
while (!q.empty()) {
int node = q.front();
q.pop();
cout << node << " ";
for (int neighbor : adj[node]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
q.push(neighbor);
}
}
}
}
int main() {
int nodes = 5;
vector<vector> adj(nodes);
adj[0] = {1, 2};
adj[1] = {0, 3, 4};
adj[2] = {0};
adj[3] = {1};
adj[4] = {1};
cout << "BFS Traversal starting from node 0: ";
bfs(0, adj);
cout << endl;
return 0;
}
In this example, BFS starts at node 0 and explores all immediate neighbors before moving deeper. Beginners can see how the queue ensures level-order traversal, making BFS ideal for exploring graphs systematically.
Program 2: BFS on a Directed Graph
This program applies BFS to a directed graph, which is important for tasks like topological sorting and dependency resolution.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
void bfsDirected(int start, vector<vector<int>> &adj) {
vector<bool> visited(adj.size(), false);
queue<int> q;
visited[start] = true;
q.push(start);
while (!q.empty()) {
int node = q.front();
q.pop();
cout << node << " ";
for (int neighbor : adj[node]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
q.push(neighbor);
}
}
}
}
int main() {
int nodes = 4;
vector<vector<int>> adj(nodes);
adj[0] = {1, 2};
adj[1] = {2};
adj[2] = {3};
adj[3] = {};
cout << "BFS on directed graph starting from node 0: ";
bfsDirected(0, adj);
cout << endl;
return 0;
}
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
void bfsDirected(int start, vector<vector<int>> &adj) {
vector visited(adj.size(), false);
queue q;
visited[start] = true;
q.push(start);
while (!q.empty()) {
int node = q.front();
q.pop();
cout << node << " ";
for (int neighbor : adj[node]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
q.push(neighbor);
}
}
}
}
int main() {
int nodes = 4;
vector<vector> adj(nodes);
adj[0] = {1, 2};
adj[1] = {2};
adj[2] = {3};
adj[3] = {};
cout << "BFS on directed graph starting from node 0: ";
bfsDirected(0, adj);
cout << endl;
return 0;
}
Here, BFS explores all reachable nodes from the start node while respecting the direction of edges. Beginners can notice that BFS adapts easily to different graph types without significant code changes.
Program 3: BFS to Find Shortest Path in an Unweighted Graph
BFS can efficiently find the shortest distance from a start node to all other nodes in an unweighted graph.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
void bfsShortestPath(int start, vector<vector<int>> &adj) {
vector<int> distance(adj.size(), -1);
queue<int> q;
distance[start] = 0;
q.push(start);
while (!q.empty()) {
int node = q.front();
q.pop();
for (int neighbor : adj[node]) {
if (distance[neighbor] == -1) {
distance[neighbor] = distance[node] + 1;
q.push(neighbor);
}
}
}
for (int i = 0; i < distance.size(); i++)
cout << "Distance from " << start << " to " << i << ": " << distance[i] << endl;
}
int main() {
int nodes = 5;
vector<vector<int>> adj(nodes);
adj[0] = {1, 2};
adj[1] = {0, 3, 4};
adj[2] = {0};
adj[3] = {1};
adj[4] = {1};
cout << "Shortest path distances from node 0:" << endl;
bfsShortestPath(0, adj);
return 0;
}
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
void bfsShortestPath(int start, vector<vector<int>> &adj) {
vector distance(adj.size(), -1);
queue q;
distance[start] = 0;
q.push(start);
while (!q.empty()) {
int node = q.front();
q.pop();
for (int neighbor : adj[node]) {
if (distance[neighbor] == -1) {
distance[neighbor] = distance[node] + 1;
q.push(neighbor);
}
}
}
for (int i = 0; i < distance.size(); i++)
cout << "Distance from " << start << " to " << i << ": " << distance[i] << endl;
}
int main() {
int nodes = 5;
vector<vector> adj(nodes);
adj[0] = {1, 2};
adj[1] = {0, 3, 4};
adj[2] = {0};
adj[3] = {1};
adj[4] = {1};
cout << "Shortest path distances from node 0:" << endl;
bfsShortestPath(0, adj);
return 0;
}
BFS ensures that each node is visited in the shortest possible order, making it perfect for finding minimum steps or levels in unweighted graphs. Beginners can visualize BFS as expanding layers of neighbors.
Program 4: BFS to Count Connected Components
This program uses BFS to identify all connected components in an undirected graph.
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
void bfsComponent(int start, vector<vector<int>> &adj, vector<bool> &visited) {
queue<int> q;
visited[start] = true;
q.push(start);
while (!q.empty()) {
int node = q.front();
q.pop();
for (int neighbor : adj[node]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
q.push(neighbor);
}
}
}
}
int main() {
int nodes = 6;
vector<vector<int>> adj(nodes);
adj[0] = {1};
adj[1] = {0, 2};
adj[2] = {1};
adj[3] = {4};
adj[4] = {3};
adj[5] = {};
vector<bool> visited(nodes, false);
int components = 0;
for (int i = 0; i < nodes; i++) {
if (!visited[i]) {
bfsComponent(i, adj, visited);
components++;
}
}
cout << "Number of connected components: " << components << endl;
return 0;
}
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
void bfsComponent(int start, vector<vector<int>> &adj, vector<bool> &visited) {
queue q;
visited[start] = true;
q.push(start);
while (!q.empty()) {
int node = q.front();
q.pop();
for (int neighbor : adj[node]) {
if (!visited[neighbor]) {
visited[neighbor] = true;
q.push(neighbor);
}
}
}
}
int main() {
int nodes = 6;
vector<vector> adj(nodes);
adj[0] = {1};
adj[1] = {0, 2};
adj[2] = {1};
adj[3] = {4};
adj[4] = {3};
adj[5] = {};
vector visited(nodes, false);
int components = 0;
for (int i = 0; i < nodes; i++) {
if (!visited[i]) {
bfsComponent(i, adj, visited);
components++;
}
}
cout << "Number of connected components: " << components << endl;
return 0;
}
This example illustrates a practical application of BFS. Beginners can see how BFS can explore and mark all nodes in a component, helping count isolated clusters in a network.
Frequently Asked Questions (FAQ)
Q1: What is Breadth-First Search (BFS)?
BFS is a graph traversal algorithm that explores nodes level by level, visiting all neighbors before moving deeper.
Q2: When should I use BFS?
Use BFS for finding shortest paths in unweighted graphs, level-order traversal, connected components, and network exploration.
Q3: How does BFS differ from DFS?
BFS explores nodes layer by layer using a queue, while DFS goes deep first using recursion or a stack.
Q4: Can BFS work on directed graphs?
Yes, BFS works on both directed and undirected graphs while respecting edge directions.
Q5: What is the time complexity of BFS?
The time complexity is O(V + E), where V is vertices and E is edges, because each node and edge is visited once.
Conclusion
Breadth-First Search is a fundamental and practical algorithm in graph theory. We explored BFS on undirected and directed graphs, used it to find shortest paths, and counted connected components. For beginners, BFS is an excellent way to understand queues, graph representation, and level-order traversal.
By practicing BFS, learners can tackle real-world problems like network analysis, routing, and pathfinding. Start with small graphs and visualize the layer-by-layer exploration to build a strong intuition. Once comfortable, BFS serves as a foundation for advanced graph algorithms and competitive programming challenges.