GeeksforGeeks Easy

BFS of Graph

Return the breadth-first traversal order of a graph given as an adjacency list.

graphbfstraversal

02

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.

03

Approach

1

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.

2

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.

3

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.

04

Solution & live demo

python

▶1from collections import deque
▶2 
▶3def bfs_of_graph(n, adj):
▶4    seen = [False] * n
▶5    order = []
▶6    for s in range(n):            # every component
▶7        if seen[s]: continue
▶8        seen[s] = True            # mark at ENQUEUE time
▶9        q = deque([s])
▶10        while q:
▶11            v = q.popleft()
▶12            order.append(v)
▶13            for u in adj[v]:      # push one hop further
▶14                if not seen[u]:
▶15                    seen[u] = True
▶16                    q.append(u)
▶17    return order

05

Edge cases

Disconnected graph

Outer loop starts a new BFS at each unvisited vertex.

Vertex reachable two ways

Marked at first enqueue, so the second edge finds it already seen.

Single vertex

Queued, popped, recorded — one step.

06

Complexity

Time

O(V + E)

Space

O(V)

Every vertex enters the queue exactly once.