BFS in Graph — Editorial

Opening the reading…

Intuitionthe queue is the order of the search

Starting from vertex 0, breadth-first search must finish with every vertex one edge away before it processes a vertex two edges away. A queue gives exactly that order: newly discovered neighbors go to the back, while vertices discovered earlier leave from the front. Scanning each adjacency list from left to right also preserves the required order within a layer.

The visited array answers whether a vertex has already been discovered, not merely whether it has already been processed. Marking at discovery time is essential because two different edges can point to the same destination. The first edge claims that vertex and places it in the queue; later edges see the mark and do nothing. This also makes cycles and self-loops harmless.

Approach

Create a visited array of size n and an empty answer vector, because each vertex needs one discovery state and the result must preserve the order in which vertices are processed.

Mark vertex 0 visited and enqueue it before the loop, because the traversal starts there and an unseeded queue would never reach any vertex.

While the queue is not empty, remove its front vertex u, because FIFO removal guarantees that vertices discovered earlier and therefore in earlier layers are processed first.

Append u to answer when it is removed, because queue removal is the moment BFS visits the vertex and gives the returned vector its traversal order.

Scan graph[u] from left to right, because adjacency-list order determines the order in which same-layer discoveries are queued.

For every neighbor v that is not visited, mark it immediately and enqueue it, because marking only on removal would allow repeated edges or converging paths to place v in the queue multiple times.

Return answer after the queue empties, because every vertex reachable from 0 has then been discovered and every unreachable vertex has correctly remained absent.

Complexityeach listed edge is examined at most once

MEASURE	BOUND	WHY
Time	O(n + m)	Each reachable vertex enters and leaves the queue once. When such a vertex is removed, its adjacency list is scanned once, so each listed edge from a reachable source is examined once and no edge is rescanned; unreachable lists only reduce the work, giving O(n + m) as the worst-case bound.
Space	O(n) extra	The visited array and the queue can each hold up to n vertices; a star-shaped graph can make the queue contain nearly all vertices at once, while a chain uses a smaller queue. The returned answer vector is required output and is excluded from the extra-space bound.

Here n is the number of vertices and m is the total number of listed directed edges across all adjacency lists.

Annotated solutionC++ · iterative queue-based BFS

CPPA complete BFS that preserves adjacency order and claims vertices when they are enqueued.

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

class Solution {
public:
    vector<int> bfsTraversal(int n, vector<vector<int>>& graph) {
        vector<int> visited(n, 0);
        vector<int> answer;
        queue<int> q;

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

        while (!q.empty()) {
            int u = q.front();
            q.pop();
            answer.push_back(u);

            for (int v : graph[u]) {
                if (!visited[v]) {
                    visited[v] = 1;
                    q.push(v);
                }
            }
        }

        return answer;
    }
};

The placement of visited[v] = 1 before q.push(v) is the key line. Suppose two edges reach v while it is still waiting in the queue. The first edge marks and enqueues it; the second edge sees the mark and skips it. If the mark happened after removal instead, both edges could create separate queue entries and the result could contain v more than once.