BFS of Graph
Return the breadth-first traversal order of a graph given as an adjacency list.
Open on GeeksforGeeks ↗Intuition
BFS explores in rings: everything one hop away, then two hops, and so on. A FIFO queue is what enforces that — newly discovered vertices go to the back, behind everything already waiting. Marking a vertex when it is enqueued (not when dequeued) is essential, otherwise a vertex reachable by two edges gets queued twice.
BFS explores by distance, which is why it — and not DFS — gives shortest paths on unweighted graphs. The critical detail is marking vertices when they're enqueued, not when dequeued: otherwise a vertex reachable from two neighbours enters the queue twice and gets processed twice.
Approach
Queue, not stack
Seed the queue with the start vertex and mark it. Repeatedly pop from the front, record it, and push its unvisited neighbours to the back.
Mark at enqueue time
If you only mark on dequeue, a vertex with two incoming edges enters the queue twice and is reported twice. Marking as it is queued guarantees exactly one visit.
Why the order is layered
Everything at distance k is queued before anything at distance k+1, so BFS also yields shortest hop-counts on an unweighted graph for free.
Solution & live demo
Common pitfalls
Marking visited at dequeue time
v = q.popleft()
seen[v] = True
for u in adj[v]:
if not seen[u]: q.append(u)for u in adj[v]:
if not seen[u]:
seen[u] = True
q.append(u)Between being enqueued and dequeued a vertex is unmarked, so any other neighbour also enqueues it — duplicates in the queue, duplicate entries in the output, and on dense graphs a blow-up in queue size. Mark it the moment it enters.
Using a list with pop(0) as the queue
q = [s] v = q.pop(0)
q = deque([s]) v = q.popleft()
list.pop(0) shifts every remaining element, so it's O(n) per dequeue and the traversal degrades to O(n²). A deque pops from the left in O(1).
Skipping the outer component loop
seen[0] = True q = deque([0])
for s in range(n):
if seen[s]: continue
seen[s] = True
q = deque([s])Same trap as DFS — one BFS only reaches one component. Disconnected vertices need their own starts.
Edge cases
Outer loop starts a new BFS at each unvisited vertex.
Marked at first enqueue, so the second edge finds it already seen.
Queued, popped, recorded — one step.