Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Breadth-First Search

MEDIUMProblemSolveExternal Links

Description

You are given a connected undirected graph with V vertices numbered from 0 to V−1. The graph is represented as an adjacency list, where adj[i] contains all the vertices that are directly connected to vertex i.

Your task is to perform a Breadth-First Search (BFS) traversal of the graph starting from vertex 0 and return the order in which vertices are visited.

BFS explores the graph level by level. It first visits the starting vertex, then all of its immediate neighbors, then the neighbors of those neighbors, and so on. When visiting the neighbors of any vertex, you must visit them in the same order they appear in the adjacency list.

Return a list of all vertices in the order they are visited during the BFS traversal.

Undirected graph with 5 nodes showing the structure for BFS traversal, with node 0 highlighted as the starting vertex
Undirected graph with 5 nodes showing the structure for BFS traversal, with node 0 highlighted as the starting vertex

Examples

Example 1

Input: adj = [[2, 3, 1], [0], [0, 4], [0], [2]]

Output: [0, 2, 3, 1, 4]

Explanation:

  • Start at vertex 0. Its neighbors in adjacency list order are [2, 3, 1].
  • Visit vertex 0 first, then enqueue its neighbors.
  • Next, visit vertex 2 (first neighbor of 0). Vertex 2's unvisited neighbor is 4.
  • Then visit vertex 3 (second neighbor of 0). Vertex 3's only neighbor (0) is already visited.
  • Then visit vertex 1 (third neighbor of 0). Vertex 1's only neighbor (0) is already visited.
  • Finally, visit vertex 4 (neighbor of 2).
  • The traversal follows the level-by-level pattern: Level 0 = {0}, Level 1 = {2, 3, 1}, Level 2 = {4}.

Example 2

Input: adj = [[1, 2], [0, 2], [0, 1, 3, 4], [2], [2]]

Output: [0, 1, 2, 3, 4]

Explanation:

  • Start at vertex 0. Neighbors in order: [1, 2].
  • Visit 0, then enqueue 1 and 2.
  • Visit 1 (neighbor of 0). Vertex 1's neighbors are [0, 2] — both already visited.
  • Visit 2 (neighbor of 0). Vertex 2's neighbors are [0, 1, 3, 4]. Nodes 0 and 1 are visited; enqueue 3 and 4.
  • Visit 3, then visit 4.
  • Traversal: Level 0 = {0}, Level 1 = {1, 2}, Level 2 = {3, 4}.

Example 3

Input: adj = [[1], [0]]

Output: [0, 1]

Explanation:

  • The graph has only two vertices connected by a single edge.
  • Start at vertex 0. Its only neighbor is 1.
  • Visit 0, then visit 1. BFS completes in two steps.

Constraints

  • 1 ≤ V = adj.size() ≤ 10^4
  • 0 ≤ adj[i][j] < V
  • The graph is connected and undirected
  • The adjacency list does not contain duplicate edges
  • There are no self-loops

Editorial

Brute Force

Intuition

If you have never seen a queue data structure before, the most natural way to implement BFS is to use a regular list (or array) as your container. You add newly discovered nodes to the back of the list and remove nodes from the front to process them.

The core BFS logic is the same: start at the source, mark it as visited, then repeatedly take the frontmost node, explore its neighbors, and add any unvisited neighbor to the back of the list. This ensures we process nodes in the order they were discovered — which is exactly what BFS requires.

The catch is subtle but important: removing an element from the front of a regular array or list is expensive. In most programming languages, when you remove the first element, every remaining element must shift one position to the left to fill the gap. If the list has k elements, this shift costs O(k) time. Over the entire traversal, these shifts accumulate into significant overhead.

Step-by-Step Explanation

Let's trace through Example 1 with adj = [[2, 3, 1], [0], [0, 4], [0], [2]]:

Step 1: Initialization

  • Create a list (acting as our container): list = [0]
  • Mark node 0 as visited: visited = {0}
  • result = []

Step 2: Process node 0

  • Remove 0 from the front of the list: list becomes []
  • (List was size 1, so no elements need to shift)
  • Add 0 to result → result = [0]
  • Explore neighbors of 0: adj[0] = [2, 3, 1]

Step 3: Visit neighbor 2

  • Node 2 is not visited → mark visited, append to list
  • visited = {0, 2}, list = [2]

Step 4: Visit neighbor 3

  • Node 3 is not visited → mark visited, append to list
  • visited = {0, 2, 3}, list = [2, 3]

Step 5: Visit neighbor 1

  • Node 1 is not visited → mark visited, append to list
  • visited = {0, 1, 2, 3}, list = [2, 3, 1]

Step 6: Process node 2

  • Remove 2 from the front of the list. The remaining elements [3, 1] must shift left by one position.
  • ⚠️ Shift cost: 2 element moves. list becomes [3, 1]
  • Add 2 to result → result = [0, 2]
  • Explore neighbors of 2: adj[2] = [0, 4]

Step 7: Check neighbor 0 of node 2

  • Node 0 is already visited → skip

Step 8: Visit neighbor 4

  • Node 4 is not visited → mark visited, append to list
  • visited = {0, 1, 2, 3, 4}, list = [3, 1, 4]

Step 9: Process node 3

  • Remove 3 from front. Elements [1, 4] shift left. Shift cost: 2 moves.
  • list becomes [1, 4]
  • Add 3 to result → result = [0, 2, 3]
  • Neighbors of 3: adj[3] = [0]. Node 0 already visited → skip.

Step 10: Process node 1

  • Remove 1 from front. Element [4] shifts left. Shift cost: 1 move.
  • list becomes [4]
  • Add 1 to result → result = [0, 2, 3, 1]
  • Neighbors of 1: adj[1] = [0]. Node 0 already visited → skip.

Step 11: Process node 4

  • Remove 4 from front. List becomes empty. No shift needed.
  • Add 4 to result → result = [0, 2, 3, 1, 4]
  • Neighbors of 4: adj[4] = [2]. Node 2 already visited → skip.

Step 12: Termination

  • List is empty. All reachable nodes visited.
  • Final result: [0, 2, 3, 1, 4]
  • Total shift operations across all removals: 0 + 2 + 2 + 1 + 0 = 5 element moves. In a graph with thousands of nodes, this overhead becomes crippling.

Algorithm

  1. Create a list and add the source vertex (0) to it
  2. Create a visited array of size V, mark vertex 0 as visited
  3. While the list is not empty:
    a. Remove the first element from the list (this shifts all remaining elements left)
    b. Add the removed node to the result
    c. For each neighbor of the removed node (in adjacency list order):
    • If the neighbor is not visited, mark it as visited and append it to the list
  4. Return the result list

Code

#include <vector>
using namespace std;

class Solution {
public:
    vector<int> bfsOfGraph(vector<vector<int>>& adj) {
        int V = adj.size();
        vector<bool> visited(V, false);
        vector<int> result;
        vector<int> frontier;

        frontier.push_back(0);
        visited[0] = true;

        while (!frontier.empty()) {
            // Remove from front — O(V) due to element shifting
            int node = frontier[0];
            frontier.erase(frontier.begin());
            result.push_back(node);

            for (int neighbor : adj[node]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    frontier.push_back(neighbor);
                }
            }
        }

        return result;
    }
};
class Solution:
    def bfsOfGraph(self, adj):
        V = len(adj)
        visited = [False] * V
        result = []
        frontier = [0]
        visited[0] = True

        while frontier:
            # Remove from front — O(V) due to element shifting
            node = frontier.pop(0)
            result.append(node)

            for neighbor in adj[node]:
                if not visited[neighbor]:
                    visited[neighbor] = True
                    frontier.append(neighbor)

        return result
import java.util.*;

class Solution {
    public ArrayList<Integer> bfsOfGraph(ArrayList<ArrayList<Integer>> adj) {
        int V = adj.size();
        boolean[] visited = new boolean[V];
        ArrayList<Integer> result = new ArrayList<>();
        ArrayList<Integer> frontier = new ArrayList<>();

        frontier.add(0);
        visited[0] = true;

        while (!frontier.isEmpty()) {
            // Remove from front — O(V) due to element shifting
            int node = frontier.remove(0);
            result.add(node);

            for (int neighbor : adj.get(node)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    frontier.add(neighbor);
                }
            }
        }

        return result;
    }
}

Complexity Analysis

Time Complexity: O(V² + E)

Each of the V vertices is removed from the front of the list exactly once. When we remove the front element from a list of size k, all remaining k−1 elements must shift left, costing O(k) time. In the worst case (a chain graph 0→1→2→...→V−1), the kth removal shifts V−k elements. The total shifting work is (V−1) + (V−2) + ... + 0 = V(V−1)/2 = O(V²). Additionally, we process each edge once during neighbor exploration, contributing O(E). Total: O(V² + E).

Space Complexity: O(V)

We use a visited array of size V and a list that holds at most V elements at any time. The result array also stores V elements. All of these are O(V).

Why This Approach Is Not Efficient

The brute force approach uses a regular list as a makeshift queue. The fundamental problem is that removing from the front of a list requires shifting every remaining element one position to the left — an O(V) operation.

Over the full BFS traversal, we perform V such removals. The total shifting work sums to V(V−1)/2, which is O(V²). With V up to 10^4, that is up to approximately 5 × 10^7 shifting operations. While this may pass for small inputs, it is wasteful and can become a bottleneck in tighter time limits or larger graphs.

The real inefficiency is conceptual: we are using the wrong data structure for a FIFO (First-In, First-Out) operation. A proper queue provides O(1) removal from the front by using either a linked list or a circular buffer. Switching to a queue reduces total dequeue work from O(V²) to O(V), bringing the overall time complexity down to O(V + E).

The key insight: BFS needs FIFO order, and a queue is the data structure designed specifically for FIFO operations. Using a list forces O(V) overhead on every single dequeue, while a queue does the same job in O(1).

Optimal Approach - BFS with Queue

Intuition

Imagine you are exploring a cave system starting from the entrance. You want to explore every room, and you want to visit the closest rooms first before venturing deeper. Here is your strategy:

  1. Stand at the entrance (vertex 0). Look at all the rooms directly connected to it.
  2. Write down those rooms on a checklist — but add them to the end of the list.
  3. Always visit the room at the front of your list next.
  4. When you visit a new room, look at its connected rooms. Add any unvisited ones to the end of the list.
  5. Keep going until your list is empty.

This is exactly how BFS works. The checklist is a queue — a data structure where items are added at the back and removed from the front (First-In, First-Out). The queue naturally ensures that closer rooms (vertices at smaller distances from the source) are visited before farther ones.

The visited array prevents us from entering the same room twice. In a graph with cycles, without this check, we would loop forever — visiting the same set of rooms endlessly. The visited array breaks these cycles by marking rooms as soon as we discover them, not when we process them.

Using a proper queue (like collections.deque in Python or std::queue in C++), both adding to the back and removing from the front are O(1) operations. This eliminates the O(V) shifting overhead of the brute force approach.

Step-by-Step Explanation

Let's trace through Example 1 with adj = [[2, 3, 1], [0], [0, 4], [0], [2]]:

Step 1: Initialization

  • Create a queue and enqueue vertex 0: queue = [0]
  • Mark vertex 0 as visited: visited = {0}
  • result = []

Step 2: Dequeue node 0

  • Dequeue 0 from the front in O(1): queue = []
  • Add 0 to result → result = [0]
  • Explore neighbors of 0: adj[0] = [2, 3, 1]

Step 3: Enqueue neighbor 2

  • Node 2 is not visited → mark visited, enqueue
  • visited = {0, 2}, queue = [2]

Step 4: Enqueue neighbor 3

  • Node 3 is not visited → mark visited, enqueue
  • visited = {0, 2, 3}, queue = [2, 3]

Step 5: Enqueue neighbor 1

  • Node 1 is not visited → mark visited, enqueue
  • visited = {0, 1, 2, 3}, queue = [2, 3, 1]
  • All of node 0's neighbors are now enqueued. The queue holds the complete Level 1 frontier.

Step 6: Dequeue node 2

  • Dequeue 2 in O(1): queue = [3, 1]
  • Add 2 to result → result = [0, 2]
  • Explore neighbors of 2: adj[2] = [0, 4]

Step 7: Skip visited neighbor 0

  • Node 0 is already visited → skip. Without this check, we would re-enqueue node 0 and eventually loop forever in this cyclic graph (0↔2).

Step 8: Enqueue neighbor 4

  • Node 4 is not visited → mark visited, enqueue
  • visited = {0, 1, 2, 3, 4}, queue = [3, 1, 4]

Step 9: Dequeue node 3

  • Dequeue 3 in O(1): queue = [1, 4]
  • Add 3 to result → result = [0, 2, 3]
  • Neighbors of 3: adj[3] = [0]. Node 0 already visited → no new enqueues.

Step 10: Dequeue node 1

  • Dequeue 1 in O(1): queue = [4]
  • Add 1 to result → result = [0, 2, 3, 1]
  • Neighbors of 1: adj[1] = [0]. Node 0 already visited → no new enqueues.

Step 11: Dequeue node 4

  • Dequeue 4 in O(1): queue = []
  • Add 4 to result → result = [0, 2, 3, 1, 4]
  • Neighbors of 4: adj[4] = [2]. Node 2 already visited → no new enqueues.

Step 12: Termination

  • Queue is empty → BFS complete.
  • Final result: [0, 2, 3, 1, 4]
  • Nodes were visited level by level: Level 0 = {0}, Level 1 = {2, 3, 1}, Level 2 = {4}.
  • Every enqueue and dequeue was O(1). Each vertex and edge was processed exactly once.

BFS Traversal — Queue-Based Level-by-Level Exploration — Watch how BFS explores the graph level by level using a queue, visiting all neighbors of the current node before moving deeper into the graph.

Algorithm

  1. Create a queue and enqueue the source vertex (0)
  2. Create a boolean visited array of size V; mark vertex 0 as visited
  3. Initialize an empty result list
  4. While the queue is not empty:
    a. Dequeue the front vertex (O(1) operation)
    b. Append the dequeued vertex to the result
    c. For each neighbor of the dequeued vertex (in adjacency list order):
    • If the neighbor has not been visited:
      • Mark it as visited
      • Enqueue it
  5. Return the result list

Code

#include <vector>
#include <queue>
using namespace std;

class Solution {
public:
    vector<int> bfsOfGraph(vector<vector<int>>& adj) {
        int V = adj.size();
        vector<bool> visited(V, false);
        vector<int> result;
        queue<int> q;

        q.push(0);
        visited[0] = true;

        while (!q.empty()) {
            int node = q.front(); // O(1)
            q.pop();              // O(1)
            result.push_back(node);

            for (int neighbor : adj[node]) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    q.push(neighbor);
                }
            }
        }

        return result;
    }
};
from collections import deque

class Solution:
    def bfsOfGraph(self, adj):
        V = len(adj)
        visited = [False] * V
        result = []
        queue = deque([0])
        visited[0] = True

        while queue:
            node = queue.popleft()  # O(1) dequeue
            result.append(node)

            for neighbor in adj[node]:
                if not visited[neighbor]:
                    visited[neighbor] = True
                    queue.append(neighbor)

        return result
import java.util.*;

class Solution {
    public ArrayList<Integer> bfsOfGraph(ArrayList<ArrayList<Integer>> adj) {
        int V = adj.size();
        boolean[] visited = new boolean[V];
        ArrayList<Integer> result = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();

        queue.add(0);
        visited[0] = true;

        while (!queue.isEmpty()) {
            int node = queue.poll(); // O(1) dequeue
            result.add(node);

            for (int neighbor : adj.get(node)) {
                if (!visited[neighbor]) {
                    visited[neighbor] = true;
                    queue.add(neighbor);
                }
            }
        }

        return result;
    }
}

Complexity Analysis

Time Complexity: O(V + E)

Each of the V vertices is enqueued and dequeued exactly once. Both operations are O(1) with a proper queue, contributing O(V) total. For each vertex we dequeue, we iterate through its adjacency list to check all neighbors. Since every edge is stored twice in an undirected graph's adjacency list (once for each endpoint), the total work across all neighbor explorations is O(2E) = O(E). Combined: O(V + E).

For the given constraints (V ≤ 10^4), the algorithm performs at most ~2 × 10^4 operations, which is extremely fast.

Space Complexity: O(V)

The visited array uses O(V) space. The queue holds at most V vertices at any point (in the worst case, all vertices are at the same level). The result array stores exactly V elements. Total auxiliary space: O(V).