BFS & DFS
Breadth-first search with a queue, depth-first search with recursion or a stack, the visited array, and O(V + E).
Rule of this site: Don't just watch: implement it yourself, then solve 2–3 problems.
02Mental model
You drop a stone in a pond. The ripples spread out ring by ring: everything 1 step away, then 2 steps, then 3. That is Breadth-First Search.
Now you explore a maze. You follow one corridor as far as it goes, and only when you hit a dead end do you back up to try the last turn you skipped. That is Depth-First Search.
BFS: use a queue
- Mark the start visited and enqueue it.
- While the queue is not empty: dequeue u, process it, and enqueue every unvisited neighbour (marking it visited now).
The queue makes vertices come out in order of distance. So BFS gives the shortest path in edges.
DFS: use a stack (or recursion)
void dfs(int u) {
visited[u] = true;
cout << u << " ";
for (int v : adj[u])
if (!visited[v]) dfs(v);
}The recursion is a stack: the call stack remembers where to back up to. An iterative version uses std::stack.
Why “visited”?
Trees have no cycles, so tree traversals never revisit a node. Graphs can have cycles: 0 → 1 → 4 → 3 → 0 → … would loop forever. The visited array makes sure every vertex is processed once.
Cost
Each vertex is enqueued (or called) once, and each edge is checked once from each end: O(V + E) with an adjacency list. With a matrix, finding a vertex’s neighbours scans a whole row, so O(V²).
Tree level-order traversal (Chapter 6) is just BFS on a tree.
03Visualize
space play · ←→ step · r reset. The highlighted code line follows each step.
Run BFS, then DFS. Compare the queue with the call stack, and the two output orders.
04C++ code
Compiled and run with g++ -std=c++17; the output below is real. Type it out yourself before you copy it.
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
void bfs(int s, const vector<vector<int>>& adj) {
vector<bool> visited(adj.size(), false);
queue<int> q;
visited[s] = true;
q.push(s);
while (!q.empty()) {
int u = q.front(); q.pop();
cout << u << " ";
for (int v : adj[u])
if (!visited[v]) {
visited[v] = true; // mark when enqueued, not when printed
q.push(v);
}
}
}
void dfs(int u, const vector<vector<int>>& adj, vector<bool>& visited) {
visited[u] = true;
cout << u << " ";
for (int v : adj[u])
if (!visited[v]) dfs(v, adj, visited);
}
void dfsIterative(int s, const vector<vector<int>>& adj) {
vector<bool> visited(adj.size(), false);
stack<int> st;
st.push(s);
while (!st.empty()) {
int u = st.top(); st.pop();
if (visited[u]) continue;
visited[u] = true;
cout << u << " ";
for (int i = adj[u].size() - 1; i >= 0; i--) // push in reverse so the smallest pops first
if (!visited[adj[u][i]]) st.push(adj[u][i]);
}
}
int main() {
vector<vector<int>> adj = {
{1, 3}, // 0
{0, 2, 4}, // 1
{1, 5}, // 2
{0, 4}, // 3
{1, 3, 5}, // 4
{2, 4}, // 5
};
cout << "BFS from 0: "; bfs(0, adj); cout << "\n";
vector<bool> vis(adj.size(), false);
cout << "DFS from 0: "; dfs(0, adj, vis); cout << "\n";
cout << "DFS (stack): "; dfsIterative(0, adj); cout << "\n";
}BFS from 0: 0 1 3 2 4 5 DFS from 0: 0 1 2 5 4 3 DFS (stack): 0 1 2 5 4 3
05Complexity
| BFS / DFS with adjacency list | O(V + E) |
|---|---|
| BFS / DFS with adjacency matrix | O(V²) |
| Extra space | O(V) for visited plus the queue or stack |
BFS finds the path with the fewest edges in an unweighted graph. DFS does not.
06Watch
Graph Traversals: BFS & DFS
Why this one: Abdul Bari traces BFS and DFS by hand. The exam format exactly.
Binary tree: Level Order Traversal
Why this one: Level-order tree traversal, which is BFS on a tree. A good warm-up.
07Exam lens
Likely questions
- Give the BFS and DFS order of a drawn graph starting from a given vertex.
- Which data structure does BFS use? DFS?
- Write BFS in C++ using an adjacency list.
- Why do we need a visited array in a graph but not in a tree?
- What is the time complexity of BFS/DFS with a list? With a matrix?
Common mistakes
- No visited array, so the search loops forever around a cycle.
- In BFS, marking a vertex visited when it is dequeued instead of enqueued (it can be enqueued twice).
- Visiting neighbours in a different order from the one the question uses (usually ascending).
- Forgetting disconnected graphs. Loop over all vertices and start a new search from each unvisited one.
08Quick check
09Practice
🟢 Trace by hand
Edges A–B, A–C, B–D, C–D, D–E, C–F. Neighbours in alphabetical order. Write the BFS from A (with the queue after each dequeue) and the DFS from A.
Show answer
BFS: dequeue A → queue B C · B → C D · C → D F · D → F E · F → E · E → empty. BFS: A B C D F E
DFS: A → B → D → C → F (back) → E. DFS: A B D C F E
🟡 Implement it
Use BFS to compute the distance (number of edges) from a source to every vertex, and count connected components with DFS.
Hint
Distance: dist[v] = dist[u] + 1 when v is first enqueued. Components: loop over all vertices, and each time you find an unvisited one, run DFS and add 1.
🔴 Solve problems
Hint
BFS or DFS from source; check whether destination is visited.
Hint
The grid is a graph where each cell has up to 4 neighbours. DFS from the start cell.
Hint
Count how many times you must start a new DFS. That is connected components on a grid.
10Mastery checklist
Tick these honestly. When every box is ticked, the topic is marked complete.