Graph Traversal — BFS & DFS

A graph is just nodes connected by edges — friends in a social network, cities on a map, web pages linked together. Traversal means visiting every node, one at a time, in some sensible order. The two classic ways are BFS (breadth-first) and DFS (depth-first). They explore the same graph but in very different shapes: BFS spreads out in rings, DFS dives deep down one path first.

The idea

BFS explores a graph level by level. Start at one node, visit all of its direct neighbors, then all of their neighbors, and so on — like ripples spreading from a stone dropped in water.

The trick that makes this work is a FIFO queue (first in, first out). You always take the oldest waiting node next, so nodes are visited in the order they were discovered. That ordering is exactly what produces the level-by-level sweep.

One detail is essential: mark a node visited the moment you enqueue it, not when you dequeue it. A graph can have cycles, so the same node may be reachable through several edges. Marking on enqueue guarantees each node enters the queue exactly once — otherwise BFS could loop forever.

Walk through it

Press Play on the right, or step with Next / Back. The graph has 6 nodes (A–F). BFS starts at A. Notice:

• A node turns green when it is visited (dequeued and processed).
• A freshly discovered neighbor turns blue as it is enqueued — that is the frontier, the nodes waiting in line.
• The queue strip at the bottom shows who is waiting, front on the left. Nodes leave from the front and join at the back.
• The order: readout records the visit order. It comes out A B C D E F — A first, then its neighbors B, C, then their neighbors, and so on.

That order is the signature of BFS: everything one edge away from the start is visited before anything two edges away.

The code, line by line

from collections import deque
 
def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()        # take from the FRONT (FIFO)
        order.append(node)
        for nb in graph[node]:
            if nb not in visited:
                visited.add(nb)        # mark on enqueue, not dequeue
                queue.append(nb)       # add to the BACK
    return order

• deque is a double-ended queue. popleft() removes from the front in O(1), which a plain list cannot do.
• We seed visited and the queue with the start node before the loop.
• The while queue loop runs until nothing is left waiting.
• Each iteration dequeues one node, records it, and scans its neighbors. Any neighbor not yet seen is marked visited and pushed to the back.

DFS is the same skeleton with one swap. Use a stack instead of a queue — replace popleft() (front) with pop() (back), and you take the newest node next instead of the oldest. That makes the search dive deep down one path before backing up. DFS is also commonly written with recursion, where the call stack is the stack.

Complexity

Why O(V + E)? Every vertex is enqueued and dequeued exactly once (V), and across the whole run we look at each edge once from each endpoint (E). The work is proportional to the size of the graph, not to anything squared. DFS has the same O(V + E) bound — the traversal order differs, the total work does not.

When to use / pitfalls

Practice