Breadth-First Search
Breadth-First Search (BFS)
Breadth-First Search (BFS) is an algorithm for searching a tree or graph data structure for a node that meets a set of criteria. It starts at the tree’s root or graph and searches/visits all nodes at the current depth level before moving on to the nodes at the next depth level. <ref name=“geeksforgeeks”>https://www.geeksforgeeks.org/breadth-first-search-or-bfs-for-a-graph/</ref>
How it works
BFS uses a queue data structure to keep track of the nodes to be visited. It also uses an array or a set to mark the nodes that have been visited, to avoid revisiting them.
The algorithm works as follows:
Choose a starting node, mark it as visited, and add it to the queue. While the queue is not empty: Dequeue a node from the queue and process it (e.g., print its value). Enqueue all its adjacent nodes that have not been visited and mark them as visited. Repeat step 2 until the queue is empty.
Complexity
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 graph. This is because every node and every edge will be explored in the worst case.
The space complexity of BFS is O(|V|), where |V| is the number of nodes in the graph. This is because the queue can hold up to |V| nodes in the worst case.
Example C++ code
Here is an example of implementing BFS in C++ using STL containers:
#include <iostream>
#include <vector>
#include <queue>
#include <set>
using namespace std;
// A simple graph class
class Graph {
int V; // number of vertices
vector<int> *adj; // adjacency list
public:
// constructor
Graph(int V) {
this->V = V;
adj = new vector<int>[V];
}
// add an edge from u to v
void addEdge(int u, int v) {
adj[u].push_back(v);
}
// BFS starting from s
void BFS(int s) {
queue<int> q; // queue for BFS
set<int> visited; // set for marking visited nodes
// mark s as visited and enqueue it
visited.insert(s);
q.push(s);
while (!q.empty()) {
// dequeue a node and print it
int v = q.front();
q.pop();
cout << v << " ";
// enqueue all adjacent nodes that are not visited
for (int u : adj[v]) {
if (visited.find(u) == visited.end()) {
visited.insert(u);
q.push(u);
}
}
}
cout << endl;
}
};
// driver code
int main() {
// create a graph with 6 vertices
Graph g(6);
// add some edges
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 3);
g.addEdge(2, 3);
g.addEdge(2, 4);
g.addEdge(3, 5);
g.addEdge(4, 5);
// BFS starting from node 0
g.BFS(0);
return 0;
}
USACO problems for BFS
Here are some USACO problems that can be solved using BFS: