##  Breadth First Search (BFS) — Codeforces Style Explanation
Difference between en1 and en2, changed 36 character(s)
↵
↵
**BFS** is one of the most important graph algorithms, especially when we want to find the **shortest path in an unweighted graph**.↵
↵
### Why BFS?↵
↵
* **DFS is not suitable** for shortest path problems because it may go deep into one branch until reaching a leaf, even if a shorter path exists.↵
* **BFS explores the graph level by level**, which guarantees that the first time we reach a node, we reached it using the **minimum number of edges**.↵
↵
### How BFS works↵
↵
* We use a **queue**↵
* Start from the source node↵
* Visit all neighbors (level 1)↵
* Then neighbors of neighbors (level 2), and so on↵
↵
Queue order example:↵
↵
```↵
X↵
x1  x2↵
x11 x12 x21 x22↵
x111 x112 x221 x222 ...↵
```↵
↵
This level-by-level traversal is exactly why BFS gives the shortest path.↵
↵
---↵
↵
##  Key Idea for Shortest Path↵
↵
* Store `(node, distance)`↵
* When we reach the destination node for the **first time**, that distance is the shortest path.↵
↵
---↵
↵
##  Problems in Your Original Code↵
↵
Let’s quickly fix the issues:↵
↵
1. `vis[node]` should be marked **when pushing**, not when popping (to avoid duplicates).↵
2. Loop should be `m` edges, not `n`.↵
3. BFS function must return something if no path exists.↵
4. Graph size should be large enough (CF style).↵
↵
---↵
↵
##  Correct BFS Implementation (Clean & CF-Ready)↵
↵
```cpp↵
#include <bits/stdc++.h>↵
using namespace std;↵
↵
const int N = 1e5 + 5;↵
vector<int> adj[N];↵
bool vis[N];↵
↵
int bfs(int start, int end) {↵
    queue<pair<int,int>> q;↵
    q.push({start, 0});↵
    vis[start] = true;↵
↵
    while (!q.empty()) {↵
        auto [node, dist] = q.front();↵
        q.pop();↵
↵
        if (node == end)↵
            return dist;↵
↵
        for (int nxt : adj[node]) {↵
            if (!vis[nxt]) {↵
                vis[nxt] = true;↵
                q.push({nxt, dist + 1});↵
            }↵
        }↵
    }↵
    return -1; // no path↵
}↵
↵
int main() {↵
    ios::sync_with_stdio(false);↵
    cin.tie(nullptr);↵
↵
    int n, m;↵
    cin >> n >> m;↵
↵
    for (int i = 0; i < m; i++) {↵
        int a, b;↵
        cin >> a >> b;↵
        adj[a].push_back(b);↵
        adj[b].push_back(a);↵
    }↵
↵
    cout << bfs(1, 5);↵
}↵
```↵
↵
---↵
↵
##  Complexity↵
↵
* **Time:** `O(n + m)`↵
* **Space:** `O(n)`↵
↵
---↵
↵
##  Final Notes (Blog Style Tips)↵
↵
* BFS = shortest path in **unweighted graphs**↵
* DFS = exploring paths, **not shortest**↵
* Always mark `visited` **when pushing to queue**↵
* BFS is basically **multi-source Dijkstra with weight = 1**↵
↵

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English Nourhan_Abo-Heba 2026-02-10 01:17:56 347
en2 English Nourhan_Abo-Heba 2026-02-06 06:02:47 36 Tiny change: '\n\n**BFS** ' -> '\n**BFS** '
en1 English Nourhan_Abo-Heba 2026-02-06 06:02:21 2583 Initial revision (published)