BFS and DFS
Queue-based traversal; shortest path in unweighted graphs; level order; connected components; multi-source BFS; grid BFS; state-space BFS.
BFS
Queue-based traversal; shortest path in unweighted graphs; level order; connected components; multi-source BFS; grid BFS; state-space BFS.
DFS
Recursive and iterative DFS, entry/exit times, parent tracking, cycle detection, connected components, path finding, and flood fill.
Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):
BFS explores vertices in order of distance, so the first time it reaches a vertex is along a shortest path (in edges). DFS entry/exit intervals nest: u is an ancestor of v in the DFS tree exactly when tin[u] < tin[v] and tout[v] < tout[u].
Output (CPython 3.13.1):
#include <bits/stdc++.h>
using namespace std;
int main() {
int V = 8;
vector<vector<int>> adj(V);
for (auto [u, v] : vector<pair<int, int>>{{0, 1}, {0, 2}, {1, 3}, {2, 3}, {3, 4}, {5, 6}}) { adj[u].push_back(v); adj[v].push_back(u); }
// BFS from 0: distances and parents
vector<int> dist(V, -1), parent(V, -1);
queue<int> q; q.push(0); dist[0] = 0;
cout << "BFS order:";
while (!q.empty()) {
int u = q.front(); q.pop();
cout << ' ' << u;
for (int v : adj[u]) if (dist[v] == -1) { dist[v] = dist[u] + 1; parent[v] = u; q.push(v); }
}
cout << "\ndistances from 0:";
for (int d : dist) cout << ' ' << d;
vector<int> path;
for (int v = 4; v != -1; v = parent[v]) path.push_back(v);
cout << "\nshortest path 0 -> 4:";
for (auto it = path.rbegin(); it != path.rend(); ++it) cout << ' ' << *it;
// DFS with entry/exit times; components over all vertices
vector<int> tin(V, -1), tout(V, -1), comp(V, -1);
int timer = 0, comps = 0;
function<void(int)> dfs = [&](int u) {
tin[u] = timer++; comp[u] = comps;
for (int v : adj[u]) if (tin[v] == -1) dfs(v);
tout[u] = timer++;
};
…BFS order: 0 1 2 3 4
distances from 0: 0 1 1 2 3 -1 -1 -1
shortest path 0 -> 4: 0 1 3 4
components: 3 (vertex 7 is isolated)
tin/tout: 0[0,9] 1[1,8] 2[3,4] 3[2,7] 4[5,6] 5[10,13] 6[11,12] 7[14,15]from collections import deque
adj = {u: [] for u in range(8)}
for u, v in [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4), (5, 6)]:
adj[u].append(v)
adj[v].append(u)
dist = {0: 0}
q = deque([0])
while q:
u = q.popleft() # deque.popleft is O(1); list.pop(0) would be O(n)
for v in adj[u]:
if v not in dist:
dist[v] = dist[u] + 1
q.append(v)
print("distances from 0:", [dist.get(u, -1) for u in range(8)])distances from 0: [0, 1, 1, 2, 3, -1, -1, -1]Advanced traversal
Multi-source BFS, bidirectional BFS, 0–1 BFS, iterative deepening, DFS timestamps, and avoiding recursion-depth failures.
Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):
Multi-source BFS starts with all sources in the queue at distance 0 — one O(R·C) pass instead of one BFS per source. 0–1 BFS keeps the deque sorted by distance (it only ever holds two distance values), giving O(V + E) without a heap.
#include <bits/stdc++.h>
using namespace std;
int main() {
// multi-source BFS: distance from every cell to the nearest 'S'
vector<string> g = {"S...#", ".#...", "...#S", "#...."};
int R = 4, C = 5;
vector<vector<int>> d(R, vector<int>(C, -1));
queue<pair<int, int>> q;
for (int r = 0; r < R; ++r) for (int c = 0; c < C; ++c) if (g[r][c] == 'S') { d[r][c] = 0; q.push({r, c}); }
int dr[] = {1, -1, 0, 0}, dc[] = {0, 0, 1, -1};
while (!q.empty()) {
auto [r, c] = q.front(); q.pop();
for (int k = 0; k < 4; ++k) {
int nr = r + dr[k], nc = c + dc[k];
if (nr < 0 || nr >= R || nc < 0 || nc >= C || g[nr][nc] == '#' || d[nr][nc] != -1) continue;
d[nr][nc] = d[r][c] + 1; q.push({nr, nc});
}
}
cout << "distance to nearest S:\n";
for (int r = 0; r < R; ++r) { for (int c = 0; c < C; ++c) cout << setw(3) << (g[r][c] == '#' ? string("#") : to_string(d[r][c])); cout << '\n'; }
// 0-1 BFS: weight-0 edges go to the front of the deque, weight-1 to the back
int V = 5;
vector<vector<pair<int, int>>> adj(V);
for (auto [u, v, w] : vector<tuple<int, int, int>>{{0, 1, 1}, {0, 2, 0}, {2, 1,
…distance to nearest S:
0 1 2 3 #
1 # 3 2 1
2 3 4 # 0
# 4 3 2 1
0-1 BFS distances: 0 0 0 1 1Quiz
? Why does BFS give shortest paths in an unweighted graph but DFS does not?
+ BFS processes vertices in nondecreasing distance order, so the first discovery uses the fewest edges. :: DFS may reach a vertex first along a long path.
- BFS uses less memory. :: Often it uses more.
- DFS cannot find paths. :: It finds paths, not shortest ones.
- Because of recursion. :: Iterative DFS has the same issue.
? In 0–1 BFS, where does a vertex reached by a 0-weight edge go?
+ The front of the deque :: Its distance equals the current one.
- The back :: That is for weight 1.
- A priority queue :: Not needed.
- It is skipped :: No.
? A recursive DFS on a path graph of 10⁶ vertices risks…
+ stack overflow from 10⁶ nested calls :: Use an explicit stack.
- wrong answers only :: It may crash outright.
- O(n²) time :: Still O(V + E).
- nothing :: Depth equals V.