Log inSign up
easyGeeksforGeeksNot Started

Breadth First Search

Given a connected undirected graph represented by an adjacency list adj, return a list containing the BFS traversal of the graph starting from vertex 0.

Graph
Solve on GeeksforGeeks
Lesson

Problem Statement

### Problem Statement

Given a connected undirected graph represented by an adjacency list adj, perform a Breadth First Search (BFS) traversal starting from vertex 0 and return a list containing the vertices in the order they are visited.

The graph contains V vertices numbered from 0 to V - 1.

---

### Examples

Example 1: ``text Input: V = 5, adj = [[1, 2, 3], [], [4], [], []] 0 / | \ 1 2 3 | 4 Output: [0, 1, 2, 3, 4] Explanation: Starting from 0, the elements at level 1 are 1, 2, and 3. The element at level 2 through 2 is 4. Thus, BFS order is 0 -> 1 -> 2 -> 3 -> 4.

Example 2: ``text Input: V = 4, adj = [[1, 2], [2], [0, 3], [3]] Output: [0, 1, 2, 3]

---

### Constraints - 1 <= V <= 10^4 - 1 <= E <= 10^4 - The graph is 0-indexed and connected.

Constraints:

  • 1 <= V <= 104
  • 1 <= E <= 104
  • 0 <= adj[i][j] < V
  • Graph is connected and 0-indexed

What You'll Learn

Key principles and algorithmic techniques you will master from this problem:

  • Understand the mechanics of FIFO queue state management in graph traversal.
  • Prevent exponential memory bloat by marking visited upon enqueue.
  • Analyze the fundamental O(V + E) time and O(V) space complexity bounds.

Pattern Recognition Trigger

How to instantly recognize this algorithmic pattern when encountering unseen interview questions:

Signals to Look For:

  • Explore vertices layer by layer starting from source
  • Shortest path in unweighted graphs
  • Level-order traversal on general graph structures

Algorithmic Decision Tree:

  • If uniform edge weights and need shortest distance or level order -> Use BFS with FIFO Queue.
  • Always maintain visited array to avoid infinite loops on graph cycles.

Connected Patterns:

Depth First SearchRotting Oranges (Multi-source BFS)Shortest Path in Binary Matrix

1. Level-by-Level Set Expansion (Without Queue)

Intuition

Instead of an explicit queue, maintain a list of current level vertices. In each round, collect all unvisited neighbors of the current level into a next level list, marking them visited, until no new vertices are discovered.

Algorithm

  1. Initialize a visited array of size V to false.
  2. Set currentLevel = [0] and visited[0] = true.
  3. While currentLevel is not empty:
  4. Add all vertices in currentLevel to the result list.
  5. Create nextLevel = [].
  6. For each vertex u in currentLevel:
  7. For each neighbor v in adj[u]:
  8. If !visited[v]: mark visited[v] = true, append v to nextLevel.
  9. Set currentLevel = nextLevel.
  10. Return the result list.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3
4class Solution {
5public:
6 std::vector<int> bfsOfGraph(int V, std::vector<std::vector<int>>& adj) {
7 std::vector<bool> visited(V, false);
8 std::vector<int> result;
9 std::vector<int> currentLevel = {0};
10 visited[0] = true;
11
12 while (!currentLevel.empty()) {
13 std::vector<int> nextLevel;
14 for (int u : currentLevel) {
15 result.push_back(u);
16 for (int v : adj[u]) {
17 if (!visited[v]) {
18 visited[v] = true;
19 nextLevel.push_back(v);
20 }
21 }
22 }
23 currentLevel = std::move(nextLevel);
24 }
25 return result;
26 }
27};
28
29int main() {
30 Solution sol;
31 std::vector<std::vector<int>> adj = {{1, 2, 3}, {}, {4}, {}, {}};
32 std::vector<int> bfs = sol.bfsOfGraph(5, adj);
33 std::cout << "BFS Traversal: ";
34 for (int x : bfs) std::cout << x << " ";
35 std::cout << "\nExpected: 0 1 2 3 4\n";
36 return 0;
37}

Time & Space Complexity

  • Time complexity: O(V + E)
  • Space complexity: O(V)

2. Standard Queue BFS with Level Count Tracking

Intuition

Processing queue elements in batches of q.size() allows precise level tracking while maintaining a single queue structure without auxiliary frontier lists.

Algorithm

  1. Create a boolean visited array of size V.
  2. Initialize queue q, push vertex 0, mark visited[0] = true.
  3. While queue is not empty:
  4. Get levelSize = q.size().
  5. For i = 0 to levelSize - 1:
  6. Pop node u from q, append u to result.
  7. For each neighbor v in adj[u]:
  8. If !visited[v]: mark visited[v] = true, push v into q.
  9. Return result.
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4
5class Solution {
6public:
7 std::vector<int> bfsOfGraph(int V, std::vector<std::vector<int>>& adj) {
8 std::vector<bool> visited(V, false);
9 std::vector<int> result;
10 std::queue<int> q;
11
12 q.push(0);
13 visited[0] = true;
14
15 while (!q.empty()) {
16 int levelSize = q.size();
17 for (int i = 0; i < levelSize; ++i) {
18 int u = q.front();
19 q.pop();
20 result.push_back(u);
21
22 for (int v : adj[u]) {
23 if (!visited[v]) {
24 visited[v] = true;
25 q.push(v);
26 }
27 }
28 }
29 }
30 return result;
31 }
32};
33
34int main() {
35 Solution sol;
36 std::vector<std::vector<int>> adj = {{1, 2, 3}, {}, {4}, {}, {}};
37 std::vector<int> bfs = sol.bfsOfGraph(5, adj);
38 std::cout << "BFS Level-Chunked: ";
39 for (int x : bfs) std::cout << x << " ";
40 std::cout << "\nExpected: 0 1 2 3 4\n";
41 return 0;
42}

Time & Space Complexity

  • Time complexity: O(V + E)
  • Space complexity: O(V)

3. Standard Continuous Streaming BFS (Canonical)

Intuition

Nodes are enqueued continuously. As soon as a node is popped, all its unvisited neighbors are immediately marked and pushed. This minimizes branch checks and auxiliary variables.

Algorithm

  1. Create a boolean visited array of size V initialized to false.
  2. Initialize FIFO queue q, push vertex 0, mark visited[0] = true.
  3. Create empty result list.
  4. While queue is not empty:
  5. Pop front vertex u from q.
  6. Append u to result list.
  7. For every neighbor v in adj[u]:
  8. If !visited[v]:
  9. Mark visited[v] = true.
  10. Push v into q.
  11. Return result list.

Continuous Queue BFS Execution

2 of 2 questions left today
Step 1 / 5
Trace timeline20% explored
Current operationSTEP 1 OF 5
Enqueue 0, visited[0]=true
Visual state
Values and pointers at this exact step
queue
FRONT → REAR
[0]
Enqueue adds at the rear · Dequeue removes from the front
Decision / next transition
q.push(0)
Why this step matters

Enqueue 0, visited[0]=true. Queue: [0]. Result: [].

Step 1 / 5
C++ SOLUTIONCLEAN & OPTIMIZED
1#include <iostream>
2#include <vector>
3#include <queue>
4
5class Solution {
6public:
7 std::vector<int> bfsOfGraph(int V, std::vector<std::vector<int>>& adj) {
8 std::vector<bool> visited(V, false);
9 std::vector<int> result;
10 std::queue<int> q;
11
12 q.push(0);
13 visited[0] = true;
14
15 while (!q.empty()) {
16 int u = q.front();
17 q.pop();
18 result.push_back(u);
19
20 for (int v : adj[u]) {
21 if (!visited[v]) {
22 visited[v] = true;
23 q.push(v);
24 }
25 }
26 }
27 return result;
28 }
29};
30
31int main() {
32 Solution sol;
33 std::vector<std::vector<int>> adj = {{1, 2, 3}, {}, {4}, {}, {}};
34 std::vector<int> bfs = sol.bfsOfGraph(5, adj);
35 std::cout << "Canonical BFS: ";
36 for (int x : bfs) std::cout << x << " ";
37 std::cout << "\nExpected: 0 1 2 3 4\n";
38 return 0;
39}

Time & Space Complexity

  • Time complexity: O(V + E)
  • Space complexity: O(V)

Approach Comparison Matrix

Side-by-side comparison of time, space, and algorithmic trade-offs across each approach:

ApproachTimeSpaceCore IdeaTrade-off / Bottleneck
1.Level-by-Level Set ExpansionO(V + E)O(V)Maintains current and next level frontier arrays without an explicit queue.Memory allocation overhead
2.Level Chunking Queue BFSO(V + E)O(V)FIFO queue with an inner loop running up to levelSize = q.size().Inner loop synchronization
3.Continuous Streaming BFS (Canonical)OptimalO(V + E)O(V)Direct streaming queue loop with immediate neighbor pushing.None

Common Pitfalls & Crucial Edge Cases

Pitfall 1:

Marking a node as visited when popping from queue rather than when pushing, leading to Memory Limit Exceeded (MLE) on dense graphs.

Pitfall 2:

Using an array shift() in JavaScript instead of pointer incrementing, causing O(V2) overall runtime.

Pitfall 3:

Forgetting that in undirected graphs, each edge is explored from both endpoints.

Crucial Edge Cases to Validate:

  • Single node graph (V = 1, adj = [[]]) — Queue pushes 0, pops 0, loop terminates immediately, returning [0].
  • Graph contains self-loops or multiple edges — The visited boolean guard prevents re-enqueuing the node on self-loops or parallel edges.
  • Disconnected graph with unvisited components — Problem specifies connected graph starting from vertex 0; for general graphs, an outer loop iterating from 0 to V-1 is required.

Interview Tips & Best Practices

How to communicate your thought process and address follow-ups in a live technical interview:

  1. Always clarify if the graph is guaranteed to be connected or if multiple components exist.
  2. Mention that BFS directly computes the shortest path in unweighted graphs.
  3. Highlight that marking visited on enqueue is a classic trap interviewers look for.

Quick Comprehension Check

Test your intuitive understanding of the core concept in 30 seconds:

1.Why MUST a vertex be marked as visited when it is pushed into the queue, rather than when it is popped?

2.What is the time complexity of BFS on an adjacency list representation with V vertices and E edges?

3.Which data structure is fundamentally required to implement Breadth First Search?

Back to DSA Sheet