↵
### 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.↵
↵
---↵
↵
##
↵
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
↵
```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**↵
↵



