BFS of Graph
BFS of Graph is a GFG problem (Easy). You are given a connected undirected graph as an adjacency list adj, where adj[i] lists the neighbours of vertex i. Return the breadth-first traversal of the graph, starting from vertex 0.
- Visit the neighbours of a vertex in the order
adj[i]lists them, left to right. - The graph can have cycles, so a vertex may be reachable along several edges. Each vertex appears in the answer once.
With up to 10⁴ vertices, the traversal has to look at each vertex and edge only a constant number of times: O(V + E).
- 1 <= adj.size() <= 10⁴
- 1 <= adj[i][j] <= 10⁴
- The graph is connected and undirected
Intuition
Breadth-first means visiting the graph in rings around vertex 0: the start, then every vertex one edge away, then every vertex two edges away.
A queue produces exactly that order. New vertices join at the back and leave from the front, so every vertex of one ring comes out before any vertex of the next. Doing BFS using a queue needs just one more rule: the graph can have cycles, so mark each vertex the moment it joins the queue, and it can never be added twice.
Reach for BFS in graph problems that ask about distance counted in edges: the fewest moves, the nearest cell, the shortest chain of words. On an unweighted graph BFS takes vertices out of the queue in order of their distance from the start, so the first time it reaches a target is along a shortest path. Rotting Oranges, 01 Matrix and Word Ladder are this same BFS graph traversal with a different rule for what counts as a neighbour.
Approach
Before reading on: in the second example ([[1,2],[0,3],[0,3,4],[1,2],[2]]), vertex 3 is a neighbour of both 1 and 2. Write down the queue after each vertex is processed. At which moment must 3 be marked so that it enters the queue only once?
Start the queue at vertex 0
Mark vertex 0 visited and put it in the queue. It is marked now, before any edge is read, so no neighbour can add it back later.
Take the vertex at the front
Remove the front vertex u with popleft() and append it to the answer. The queue hands vertices back in the order they were found, nearest first, so this is where u gets its place in the breadth-first order.
Queue each new neighbour
Walk adj[u] from left to right. For each neighbour v:
- not visited yet: mark it and append it to the back of the queue;
- already visited: skip it, since it is already waiting in the queue or already in the answer.
Marking at enqueue time is what keeps a vertex with two edges into it from being queued twice.
Stop when the queue is empty
An empty queue means every vertex reachable from 0 has been taken out once. Each vertex enters the queue once and each edge is checked from both ends, so the BFS of graph runs in O(V + E) time and O(V) extra space.
BFS of Graph solution in Python | C++ | Java
adj[0] lists them, are the next ring of the search.adj[0] lists them, are the next ring of the search.Common pitfalls
Marking a vertex when it leaves the queue
u = q.popleft()
visited[u] = True
for v in adj[u]:
if not visited[v]:
q.append(v)for v in adj[u]:
if not visited[v]:
visited[v] = True
q.append(v)Between entering and leaving the queue the vertex is unmarked, so a second neighbour queues it again. In the second example vertex 3 is queued by both 1 and 2 and shows up twice in the answer.
Using a Python list with pop(0) as the queue
q = [0] u = q.pop(0)
q = deque([0]) u = q.popleft()
list.pop(0) shifts every remaining element left, which is O(V) per removal and O(V²) overall. deque.popleft() is O(1).
Complexity
BFS of Graph FAQ
What is the difference between BFS and DFS of a graph?
BFS uses a queue and finishes every vertex at distance k before any at distance k + 1. DFS uses a stack or recursion and follows one path as deep as it goes before backing up. Both run in O(V + E), but only a BFS graph traversal gives shortest paths in an unweighted graph.
How do you run BFS on a disconnected graph?
Loop over every vertex. Whenever one is still unvisited, mark it, queue it and run the same BFS loop from it. Each start covers one connected component, and the total work stays O(V + E). This problem promises a connected graph, so one start at 0 is enough.