Breadth First Search (BFS) in C++

Yasin Cakal

Breadth-first search (BFS) is an algorithm used to traverse a graph or tree structure. It is often used in pathfinding and network traversal, and is also known as a level-order traversal. BFS is a popular choice for many graph-related problems, as it is often more efficient than depth-first search (DFS). In this article, we’ll look at how the algorithm works, its time complexity, and its space complexity. We’ll also provide some examples of BFS in C++ to help you understand the algorithm.

What is Breadth First Search (BFS)?

Breadth-first search is a graph traversal algorithm that starts at the root node and explores all the neighboring nodes before moving to the next level neighbors. As such, it traverses the graph level by level, and each level is explored completely before the next level is explored. The algorithm works by keeping track of the nodes in a queue, and it starts by adding the root node to the queue. Then, it explores the first node in the queue, adding its children to the queue, and then exploring the next node in the queue. This process continues until all nodes have been explored or until the desired node is found.

BFS in C++

To help you understand the BFS algorithm, let’s look at an example in C++. The following code implements the BFS algorithm in C++. First, we declare an array to store the visited nodes. Then, we create a queue to store the nodes that need to be visited. In the main loop, we check if the queue is empty or not. If it’s not empty, we remove the first element of the queue and add it to the visited array. Then, we check if the current node has any children and if it does, we add them to the queue. Finally, we repeat this process until all nodes have been visited.

//BFS in C++ 
#include <iostream> 
#include <queue> 
#include <vector> 

using namespace std; 

// Array to store the visited nodes 
bool visited[100]; 

// Function to perform the BFS 
void bfs(vector<int> adj[], int source) 
{ 
	// Create a queue and add the source node 
	queue<int> q; 
	q.push(source); 
	visited[source] = true; 

	while (!q.empty()) 
	{ 
		// Take the front node from the queue 
		int front = q.front();
		q.pop(); 

		// Visit all the nodes in the adjacency list of the node 
		for (int i = 0; i < adj[front].size(); i++) 
		{ 
			if (!visited[adj[front][i]]) 
			{ 
				visited[adj[front][i]] = true; 
				q.push(adj[front][i]); 
			} 
		} 
	} 
} 

int main() 
{ 
	// Adjacency list for the graph 
	vector<int> adj[100]; 

	// Code for adding edges 
	// ...

	// Perform BFS on the graph 
	bfs(adj, 0); 

	// Print the result 
	// ...

	return 0; 
}

Time and Space Complexity of Breadth First Search (BFS)

The time complexity of BFS depends on the number of nodes in the graph and the number of edges. In the worst case, the time complexity of BFS is O(V+E), where V is the number of nodes and E is the number of edges. In the best case, it is O(V).

The space complexity of BFS is O(V), as it requires an array to keep track of the visited nodes. Additionally, it requires a queue to store the nodes to be visited.

Conclusion

In this article, we looked at the Breadth First Search (BFS) algorithm and how it works. We also looked at its time and space complexity, and provided an example implementation in C++. BFS is a popular choice for many graph-related problems, as it is often more efficient than depth-first search (DFS).

Exercises

Write a C++ program to perform a Breadth First Search on a graph represented by an adjacency matrix.

#include <iostream> 
#include <queue> 
#include <vector> 

using namespace std; 

// Array to store the visited nodes 
bool visited[100]; 

// Function to perform the BFS 
void bfs(int adj[][100], int source, int n) 
{ 
	// Create a queue and add the source node 
	queue<int> q; 
	q.push(source); 
	visited[source] = true; 

	while (!q.empty()) 
	{ 
		// Take the front node from the queue 
		int front = q.front();
		q.pop(); 

		// Visit all the nodes in the adjacency list of the node 
		for (int i = 0; i < n; i++) 
		{ 
			if (adj[front][i] == 1 && !visited[i]) 
			{ 
				visited[i] = true; 
				q.push(i); 
			} 
		} 
	} 
} 

int main() 
{ 
	// Adjacency matrix for the graph 
	int adj[100][100]; 
	int n; // Number of nodes 

	// Code for taking input 
	// ...

	// Perform BFS on the graph 
	bfs(adj, 0, n); 

	// Print the result 
	// ...

	return 0; 
}

Write a C++ program to perform a Breadth First Search on a binary tree.

#include <iostream> 
#include <queue> 

using namespace std; 

// Node structure for a binary tree 
struct Node 
{ 
	int data; 
	Node *left, *right; 
}; 

// Function to perform the BFS 
void bfs(Node *root) 
{ 
	// Create a queue and add the root node 
	queue<Node *> q; 
	q.push(root); 

	while (!q.empty()) 
	{ 
		// Take the front node from the queue 
		Node *front = q.front();
		q.pop(); 

		// Print the node data 
		cout << front->data << " "; 

		// Visit the left and right nodes 
		if (front->left != NULL) 
			q.push(front->left); 
		if (front->right != NULL) 
			q.push(front->right); 
	} 
} 

int main() 
{ 
	// Binary tree 
	Node *root; 

	// Code for creating the binary tree 
	// ...

	// Perform BFS on the binary tree 
	bfs(root); 

	return 0; 
}

Write a C++ program to find the shortest path between two nodes in a graph using Breadth First Search.

#include <iostream> 
#include <queue> 
#include <vector> 

using namespace std; 

// Array to store the visited nodes 
bool visited[100]; 

// Array to store the distances of each node 
int dist[100]; 

// Function to perform the BFS 
void bfs(vector<int> adj[], int source, int destination) 
{ 
	// Create a queue and add the source node 
	queue<int> q; 
	q.push(source); 
	visited[source] = true; 
	dist[source] = 0; 

	while (!q.empty()) 
	{ 
		// Take the front node from the queue 
		int front = q.front();
		q.pop(); 

		// Visit all the nodes in the adjacency list of the node 
		for (int i = 0; i < adj[front].size(); i++) 
		{ 
			if (!visited[adj[front][i]]) 
			{ 
				visited[adj[front][i]] = true; 
				dist[adj[front][i]] = dist[front] + 1; 
				q.push(adj[front][i]); 
			} 
		} 
	} 
	
	// Print the shortest path 
	cout << "The shortest path is: " << dist[destination] << endl; 
} 

int main() 
{ 
	// Adjacency list for the graph 
	vector<int> adj[100]; 
	int source, destination; 

	// Code for adding edges 
	// ...

	// Perform BFS on the graph 
	bfs(adj, source, destination); 

	return 0; 
}

Write a C++ program to traverse a graph using Breadth First Search and check if a given node exists in the graph.

#include <iostream> 
#include <queue> 
#include <vector> 

using namespace std; 

// Array to store the visited nodes 
bool visited[100]; 

// Function to perform the BFS 
bool bfs(vector<int> adj[], int source, int dest) 
{ 
	// Create a queue and add the source node 
	queue<int> q; 
	q.push(source); 
	visited[source] = true; 

	while (!q.empty()) 
	{ 
		// Take the front node from the queue 
		int front = q.front();
		q.pop(); 

		// Visit all the nodes in the adjacency list of the node 
		for (int i = 0; i < adj[front].size(); i++) 
		{ 
			if (!visited[adj[front][i]]) 
			{ 
				visited[adj[front][i]] = true; 
				q.push(adj[front][i]); 
				
				// Check if the node is the destination node 
				if (adj[front][i] == dest) 
					return true; 
			} 
		} 
	} 
	
	// Node does not exist in the graph 
	return false; 
} 

int main() 
{ 
	// Adjacency list for the graph 
	vector<int> adj[100]; 
	int source, destination; 

	// Code for adding edges 
	// ...

	// Perform BFS on the graph 
	if (bfs(adj, source, destination)) 
		cout << "Node exists in the graph" << endl; 
	else
		cout << "Node does not exist in the graph" << endl; 

	return 0; 
}

Write a C++ program to print the level order traversal of a binary tree using Breadth First Search.

#include <iostream> 
#include <queue> 

using namespace std; 

// Node structure for a binary tree 
struct Node 
{ 
	int data; 
	Node *left, *right; 
}; 

// Function to perform the BFS 
void bfs(Node *root) 
{ 
	// Create a queue and add the root node 
	queue<Node *> q; 
	q.push(root); 

	while (!q.empty()) 
	{ 
		// Take the front node from the queue 
		Node *front = q.front();
		q.pop(); 

		// Print the node data 
		cout << front->data << " "; 

		// Visit the left and right nodes 
		if (front->left != NULL) 
			q.push(front->left); 
		if (front->right != NULL) 
			q.push(front->right); 
	} 
} 

int main() 
{ 
	// Binary tree 
	Node *root; 

	// Code for creating the binary tree 
	// ...

	// Perform BFS on the binary tree 
	bfs(root); 

	return 0; 
}

Data Structures and Algorithms with C++

Participants 943