Graph Traversal — BFS & DFS
Graph traversal means visiting all reachable vertices/nodes of a graph systematically.
The two most important graph traversal techniques are:
- BFS — Breadth-First Search
- DFS — Depth-First Search
1. Why Do We Need Graph Traversal?
Suppose we have:
0 / \ 1 2 / \ \ 3 4 5
If we want to visit every node, we need some systematic method.
For example:
BFS:
0 → 1 → 2 → 3 → 4 → 5
It visits level by level.
DFS:
0 → 1 → 3 → 4 → 2 → 5
It goes as deep as possible first.
2. Graph Representation
Before traversal, we need to represent the graph.
The most common representation is an adjacency list.
For:
0 / \ 1 2 / \ \ 3 4 5
Adjacency list:
0 → 1, 2 1 → 0, 3, 4 2 → 0, 5 3 → 1 4 → 1 5 → 2
In C++:
vector<vector<int>> graph = { {1, 2}, {0, 3, 4}, {0, 5}, {1}, {1}, {2} };
3. The visited Array
A very important concept in graph traversal is:
visited[]
Why?
Because graphs can contain cycles.
Example:
0 ─── 1 │ │ └── 2 ┘
If we keep visiting neighbors without remembering visited nodes, we could go:
0 → 1 → 2 → 0 → 1 → 2 → ...
This can continue forever.
So we maintain:
vector<bool> visited(n, false);
Initially:
visited: 0 0 0 0 0 0
When we visit node 0:
1 0 0 0 0 0
4. BFS — Breadth-First Search
BFS = Breadth-First Search
BFS visits nodes level by level.
It uses a:
Queue
Remember:
Queue = FIFO First In → First Out
5. BFS Example
Consider:
0 / \ 1 2 / \ \ 3 4 5
Starting from 0.
Level 0
0
Level 1
1 2
Level 2
3 4 5
Therefore:
BFS = 0 1 2 3 4 5
6. BFS Step-by-Step
Start:
Queue = [0]
Visit 0.
Its neighbors:
1, 2
Add them:
Queue = [1, 2]
Remove 1:
Queue = [2]
Add 1's unvisited neighbors:
3, 4
Queue = [2, 3, 4]
Remove 2:
Queue = [3, 4]
Add 5:
Queue = [3, 4, 5]
Then visit:
3 4 5
Final:
0 → 1 → 2 → 3 → 4 → 5
7. BFS C++ Code
#include <iostream> #include <vector> #include <queue> using namespace std; void bfs(int start, vector<vector<int>>& graph) { int n = graph.size(); vector<bool> visited(n, false); queue<int> q; // Mark start as visited visited[start] = true; // Put start into queue q.push(start); while (!q.empty()) { int node = q.front(); q.pop(); cout << node << " "; // Visit all neighbors for (int neighbor : graph[node]) { if (!visited[neighbor]) { visited[neighbor] = true; q.push(neighbor); } } } }
Example:
int main() { vector<vector<int>> graph = { {1, 2}, {0, 3, 4}, {0, 5}, {1}, {1}, {2} }; bfs(0, graph); return 0; }
Output:
0 1 2 3 4 5
8. Why Mark visited Before push()?
This is important.
Correct:
if (!visited[neighbor]) { visited[neighbor] = true; q.push(neighbor); }
We mark it immediately when adding it to the queue.
Otherwise, the same node could be added multiple times from different neighbors.
9. BFS Shortest Path
One of the most important applications of BFS is:
Shortest path in an unweighted graph
Example:
0 ─ 1 ─ 3 │ 2 ─ 4
Starting from 0:
Distance from 0: 0 = 0 1 = 1 2 = 1 3 = 2 4 = 2
BFS naturally explores:
distance 0 ↓ distance 1 ↓ distance 2 ↓ distance 3
Therefore, the first time BFS reaches a node, it has found the shortest number of edges from the source.
10. BFS Distance Code
vector<int> distance(n, -1); queue<int> q; distance[start] = 0; q.push(start); while (!q.empty()) { int node = q.front(); q.pop(); for (int neighbor : graph[node]) { if (distance[neighbor] == -1) { distance[neighbor] = distance[node] + 1; q.push(neighbor); } } }
For example:
distance[0] = 0 distance[1] = 1 distance[2] = 1 distance[3] = 2
11. DFS — Depth-First Search
Now let's look at DFS.
DFS = Depth-First Search
DFS explores as deeply as possible before coming back.
DFS uses:
- Recursion, or
- Stack
Remember:
Stack = LIFO Last In → First Out
12. DFS Example
Again:
0 / \ 1 2 / \ \ 3 4 5
Starting at 0.
DFS can go:
0 ↓ 1 ↓ 3
3 has no unvisited neighbor, so backtrack:
0 ↓ 1 ↘ 4
Then backtrack to 0:
0 \ 2 \ 5
One valid DFS order:
0 1 3 4 2 5
13. Recursive DFS
The most common implementation uses recursion.
void dfs( int node, vector<vector<int>>& graph, vector<bool>& visited ) { visited[node] = true; cout << node << " "; for (int neighbor : graph[node]) { if (!visited[neighbor]) { dfs(neighbor, graph, visited); } } }
Call it:
vector<bool> visited(graph.size(), false); dfs(0, graph, visited);
14. How Recursive DFS Works
Suppose:
0 → 1 → 3
Call:
dfs(0)
Then:
dfs(0) ↓ dfs(1) ↓ dfs(3)
When 3 finishes:
dfs(3) ↑ dfs(1) ↑ dfs(0)
This is called:
Backtracking
The function returns to the previous node after finishing the deeper node.
The function call stack automatically behaves like a stack.
15. DFS Using an Explicit Stack
We can also avoid recursion.
void dfs(int start, vector<vector<int>>& graph) { int n = graph.size(); vector<bool> visited(n, false); stack<int> st; st.push(start); while (!st.empty()) { int node = st.top(); st.pop(); if (visited[node]) continue; visited[node] = true; cout << node << " "; for (int neighbor : graph[node]) { if (!visited[neighbor]) { st.push(neighbor); } } } }
Here:
DFS → Stack BFS → Queue
16. BFS vs DFS
| Feature | BFS | DFS |
|---|---|---|
| Full form | Breadth First Search | Depth First Search |
| Uses | Queue | Stack / Recursion |
| Strategy | Level by level | Go deep first |
| Shortest path in unweighted graph | ✅ | ❌ |
| Cycle detection | ✅ | ✅ |
| Connected components | ✅ | ✅ |
| Topological sort | Possible | Very common |
| Maze solving | Possible | Very common |
| Memory | Can be large for wide graphs | Can be large for deep graphs |
17. Connected Components
Consider:
0 ─ 1 ─ 2 3 ─ 4 5
There are three separate components:
Component 1: 0 1 2 Component 2: 3 4 Component 3: 5
We can count them using DFS/BFS.
int components = 0; vector<bool> visited(n, false); for (int i = 0; i < n; i++) { if (!visited[i]) { components++; dfs(i, graph, visited); } }
Result:
components = 3
This is a very common DSA problem.
18. DFS for Cycle Detection
Consider:
0 ─ 1 │ │ └─2─┘
There is a cycle:
0 → 1 → 2 → 0
During DFS, if we encounter an already visited node that isn't simply the parent we came from, we can detect a cycle in an undirected graph.
Concept:
if (!visited[neighbor]) { dfs(neighbor, node); } else if (neighbor != parent) { // cycle found }
19. BFS and DFS on Trees
An important connection:
A tree is also a graph.
For a binary tree:
1 / \ 2 3 / \ 4 5
DFS gives traversals such as:
Preorder: 1 2 4 5 3
BFS gives:
Level Order: 1 2 3 4 5
So you can think:
Tree │ ├── DFS → Preorder / Inorder / Postorder │ └── BFS → Level Order
20. BFS and DFS Complexity
For an adjacency list:
V = number of vertices E = number of edges
Both BFS and DFS take:
Time = O(V + E)
Why?
Each vertex is visited once:
O(V)
And each edge is examined:
O(E)
Therefore:
O(V + E)
Extra space:
O(V)
because of:
visited[] queue / stack
21. Important Graph Traversal Problems
After learning BFS and DFS, you should be able to solve:
Beginner
- Traverse a graph
- Count vertices
- Count edges
- Search for a node
- Check whether a path exists
- Count connected components
Intermediate
- Shortest path in an unweighted graph
- Detect cycle
- Number of islands
- Flood fill
- Bipartite graph
- Rotten oranges
- Clone graph
Advanced
- Topological sorting
- Course schedule
- Dijkstra
- 0-1 BFS
- Strongly connected components
- Bridges
- Articulation points
22. The Most Important Mental Model
Remember these two:
BFS ↓ Queue ↓ Level by Level ↓ Shortest path in unweighted graph
And:
DFS ↓ Stack / Recursion ↓ Go Deep ↓ Backtrack
23. Complete BFS + DFS Example
#include <iostream> #include <vector> #include <queue> using namespace std; // BFS void bfs(int start, vector<vector<int>>& graph) { int n = graph.size(); vector<bool> visited(n, false); queue<int> q; visited[start] = true; q.push(start); while (!q.empty()) { int node = q.front(); q.pop(); cout << node << " "; for (int neighbor : graph[node]) { if (!visited[neighbor]) { visited[neighbor] = true; q.push(neighbor); } } } } // DFS void dfs( int node, vector<vector<int>>& graph, vector<bool>& visited ) { visited[node] = true; cout << node << " "; for (int neighbor : graph[node]) { if (!visited[neighbor]) { dfs(neighbor, graph, visited); } } } int main() { vector<vector<int>> graph = { {1, 2}, {0, 3, 4}, {0, 5}, {1}, {1}, {2} }; cout << "BFS: "; bfs(0, graph); cout << "\n"; vector<bool> visited(graph.size(), false); cout << "DFS: "; dfs(0, graph, visited); return 0; }
Output:
BFS: 0 1 2 3 4 5 DFS: 0 1 3 4 2 5
Final Summary
GRAPH TRAVERSAL | ┌─────────┴─────────┐ ↓ ↓ BFS DFS | | Queue Stack / Recursion | | Level by level Go deep first | | Shortest unweighted Backtracking path useful useful
The key complexity to remember:
BFS = O(V + E) DFS = O(V + E)