BFS explores a graph level by level starting from a source node. Using a queue, it processes all nodes at distance 1, then distance 2, and so on. BFS finds the shortest path in unweighted graphs and is the basis for level-order tree traversal, bipartite checking, and web crawlers.
void bfs(vector<vector<int>>& adj, int src, int n) {
vector<bool> visited(n, false);
queue<int> q;
visited[src]=true; q.push(src);
while (!q.empty()) {
int v=q.front(); q.pop();
cout << v << " ";
for (int u : adj[v])
if (!visited[u]) { visited[u]=true; q.push(u); }
}
}BFS uses a queue (FIFO) to ensure nodes are processed in order of their distance from the source. All nodes at distance d are processed before any node at distance d+1.
In an unweighted graph, the first time BFS reaches a node it has found the shortest path (minimum number of edges). Store parent pointers to reconstruct the path.
A visited set (or boolean array) prevents processing the same node twice. Without it, BFS would loop forever in graphs with cycles.
BFS is used for: shortest path in unweighted graphs, finding all nodes at distance k, checking if a graph is bipartite, finding connected components, and web crawlers.
BFS uses which data structure?
BFS on an unweighted graph finds:
Time complexity of BFS is: