What is BFS?
Breadth-First Search (BFS) is a technique to navigate through a graph by systematically examining each vertex's neighbors before progressing to the subsequent level of vertices. This method is valuable for determining the most concise route between two vertices within a graph and identifying the graph's interconnected segments. Additionally, BFS is applied in the context of topological sorting, a sequential arrangement of vertices in a directed acyclic graph (DAG) ensuring that each vertex precedes its adjacent vertex based on the defined edge direction.
In this guide, we will explore the implementation of Breadth-First Search (BFS) in C++. Initially, we will delve into the fundamental idea behind BFS and analyze its time complexity. Subsequently, we will cover the creation of a graph representation in C++ through an adjacency list and the process of graph traversal utilizing the BFS algorithm.
Concept of BFS
Breadth-First Search (BFS) is a method used to navigate through a graph by systematically examining each vertex and then moving on to its adjacent vertices before progressing to the next level. The approach involves maintaining a queue of vertices awaiting exploration, commencing with the initial vertex. During each iteration, a vertex is dequeued and its unexplored neighbors are enqueued for subsequent investigation. This cycle persists until all vertices in the queue have been traversed.
The Breadth-First Search (BFS) algorithm operates with a time complexity of O(V+E), where V stands for the quantity of vertices and E represents the quantity of edges within the graph. This characteristic renders it particularly appropriate for dense graphs, wherein the quantity of edges closely aligns with the quantity of vertices.
Representing a Graph in C++
There exist various methods to depict a graph in C++. One prevalent approach involves utilizing an adjacency list, which comprises a list of vertices that are connected to a specific vertex. For instance, contemplate the subsequent graph containing 5 vertices:
We can illustrate this graph by utilizing an adjacency list in the following manner:
vector<vector<int>> adj_list = {
{1, 3}, // vertex 0 has neighbors 1 and 3
{0, 4}, // vertex 1 has neighbors 0 and 4
{1, 5}, // vertex 2 has neighbors 1 and 5
{0, 4}, // vertex 3 has neighbors 0 and 4
{1, 3, 5}, // vertex 4 has neighbors 1, 3, and 5
{2, 4} // vertex 5 has neighbors 2 and 4
};
Here, adj_list[i] represents a vector that holds the adjacent vertices of vertex i.
Implementing BFS in C++
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
// This function performs a BFS search on a graph represented as an adjacency list.
// The graph is assumed to be undirected.
//
// Parameters:
// - adj_list: a vector of vectors representing the adjacency list of the graph
// - start: the index of the starting vertex
// - target: the index of the target vertex (optional)
//
// Returns:
// - a vector of integers representing the BFS traversal order of the graph,
// starting from the start vertex
// - an empty vector if the target vertex is not found (when the target is specified)
vector<int> bfs(const vector<vector<int>>& adj_list, int start, int target = -1)
{
int n = adj_list.size();
vector<bool> visited(n, false); // a boolean array to track visited vertices
vector<int> order; // a vector to store the BFS traversal order
queue<int> q; // a queue to hold the vertices to be visited
q.push(start); // add the starting vertex to the queue
visited[start] = true; // mark the starting vertex as visited
while (!q.empty())
{
int u = q.front(); // get the next vertex in the queue
q.pop(); // remove the vertex from the queue
order.push_back(u); // add the vertex to the traversal order
// add all the unvisited neighbors of u to the queue
for (int v : adj_list[u])
{
if (!visited[v])
{
q.push(v);
visited[v] = true;
}
}
}
if (target != -1 && !visited[target])
{
// the target vertex was not found, return an empty vector
return {};
}
return order;
}
int main()
{
// create an adjacency list for a graph with 5 vertices
vector<vector<int>> adj_list = {
{1, 2}, // vertex 0 has neighbors 1 and 2
{0, 3, 4}, // vertex 1 has neighbors 0, 3, and 4
{0, 4}, // vertex 2 has neighbors 0 and 4
{1, 4}, // vertex 3 has neighbors 1 and 4
{1, 2, 3} // vertex 4 has neighbors 1, 2, and 3
};
// perform a BFS search starting from vertex 0
vector<int> order = bfs(adj_list, 0);
// print the traversal order
cout << "BFS traversal order: ";
for (int i : order)
{
cout << i << " ";
}
cout << endl;
return 0;
}
Output:
Explanation:
In this script, we initially establish the bfs method, which accepts an adjacency list named adj_list, a beginning vertex start, and an optional target vertex target. The bfs function sets up a boolean array called visited to keep record of the visited vertices and a vector named order to save the BFS traversal sequence. It additionally constructs a queue q to manage the vertices awaiting visitation.
The function proceeds by including the initial vertex in the queue and flagging it as visited. Subsequently, it initiates a loop that persists until the queue is devoid of elements. In each cycle of the loop, the subsequent vertex is extracted from the queue and appended to the traversal sequence. Following this, all unvisited neighboring vertices are appended to the queue and labeled as visited.
If a specific target vertex is provided but cannot be located, the function will yield an empty vector. Otherwise, it will provide the order in which the traversal occurred.
In the main method, we establish an adjacency list for a graph containing 5 vertices. Subsequently, we execute a breadth-first search commencing from vertex 0 and save the sequence of traversal in the order vector. Ultimately, we display the traversal sequence on the console.
