# Breadth-First Search (BFS) — Graph Traversal & Shortest Paths (C++) ## Overview BFS visits vertices in increasing order of distance (number of edges) from the source. It's the canonical method for shortest paths in **unweighted** graphs and can detect cycles for undirected graphs when used carefully. ## Properties - Time: **O(V + E)** - Space: **O(V)** - Yields the shortest path (fewest edges) from source in unweighted graphs. ## Implementation highlights (from repo) File: `https://github.com/mashrur-rahman-fahim/algorithm/blob/main/bfs.cpp` The implementation uses a queue, `vis[]`, `lvl[]`, and `prnt[]` to track visited status, level (distance), and parent to reconstruct paths. ### Key snippet ```cpp\nqueue<int> q; q.push(s); vis[s]=1; lvl[s]=1; while (!q.empty()) { int x = q.front(); q.pop(); for (int v : adj[x]) if (!vis[v]) { prnt[v]=x; lvl[v]=lvl[x]+1; q.push(v); } }\n``` ## Uses - Shortest unweighted path - Level-order traversal - Bipartite checks and cycle detection (with small modifications) ## Source `https: //github.com/mashrur-rahman-fahim/algorithm/blob/main/bfs.cpp`.