How It Works

This chapter takes one small graph and traces, step by step, the order in which BFS, DFS and topological sorting process its vertices. Tracing by hand makes it obvious why a queue and a stack produce different orders.

The example graph

Six vertices, 0 to 5, joined by seven undirected edges. Neighbors are examined in increasing order.

graph = {
    0: [1, 2],
    1: [0, 3],
    2: [0, 3, 4],
    3: [1, 2, 5],
    4: [2, 5],
    5: [3, 4],
}

Tracing BFS

BFS puts the start vertex in a queue. Each time it removes a vertex, it appends the unvisited neighbors to the back. The key detail: mark a vertex as visited and record its distance when you enqueue it. Marking on dequeue lets the same vertex enter the queue several times.

The visit order is 0, 1, 2, 3, 4, 5 and the distances from 0 are {0: 0, 1: 1, 2: 1, 3: 2, 4: 2, 5: 3}. Because a queue is first in, first out, every vertex at distance 1 is processed before any vertex at distance 2. That layer-by-layer property is exactly why the first distance BFS assigns to a vertex is its shortest distance.

If you also record each vertex's parent (the vertex it was discovered from), you can rebuild paths. Here the parents are 1←0, 2←0, 3←1, 4←2, 5←3, so walking back from 5 gives the shortest path 0→1→3→5.

from collections import deque

def bfs_trace(graph, start):
    dist, queue = {start: 0}, deque([start])
    while queue:
        node = queue.popleft()
        added = []
        for nxt in graph[node]:
            if nxt not in dist:
                dist[nxt] = dist[node] + 1
                queue.append(nxt)
                added.append(nxt)
        print(f"dequeued {node}, added {added}, queue {list(queue)}")
    return dist

Tracing DFS

DFS steps into one neighbor immediately and only comes back when there is nowhere left to go, then tries the next neighbor. Written recursively, the call stack remembers where to return.

The visit order is 0, 1, 3, 2, 4, 5. It does not follow distance, so a path found by DFS is not necessarily shortest: 0→1→3→2→4→5 is a long detour to reach 5.

An iterative DFS with an explicit stack reproduces the recursive order if you push neighbors in reverse and mark vertices when you pop them.

def dfs_iterative(graph, start):
    order, seen, stack = [], set(), [start]
    while stack:
        node = stack.pop()
        if node in seen:
            continue
        seen.add(node)
        order.append(node)
        for nxt in reversed(graph[node]):
            if nxt not in seen:
                stack.append(nxt)
    return order

print(dfs_iterative(graph, 0))  # [0, 1, 3, 2, 4, 5]

Tracing a topological sort (Kahn's algorithm)

A topological order lists the vertices of a directed graph so that for every edge u→v, u comes before v. It exists only for DAGs. Take course prerequisites: 0→1, 0→2, 1→3, 2→3, 3→4.

Kahn's algorithm queues every vertex with in-degree 0 (no incoming edges). Each time it removes one, it deletes that vertex's outgoing edges, lowering its neighbors' in-degrees, and queues any neighbor that drops to 0.

All five vertices made it into the output, so there is no cycle. Vertices on a cycle never reach in-degree 0, so with a cycle the output ends up shorter than V. That is how Kahn's algorithm doubles as a cycle detector.

from collections import deque

def kahn(n, edges):
    adj = [[] for _ in range(n)]
    indeg = [0] * n
    for u, v in edges:
        adj[u].append(v)
        indeg[v] += 1
    queue = deque(i for i in range(n) if indeg[i] == 0)
    order = []
    while queue:
        u = queue.popleft()
        order.append(u)
        for v in adj[u]:
            indeg[v] -= 1
            if indeg[v] == 0:
                queue.append(v)
    return order if len(order) == n else None  # None means a cycle

print(kahn(5, [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)]))  # [0, 1, 2, 3, 4]

Summary

BFS grows outward in distance order using a queue, and marking on enqueue prevents duplicates. DFS dives deep and backtracks using a stack or recursion; an iterative version that pushes neighbors in reverse matches the recursive order. Kahn's algorithm peels off in-degree-0 vertices to build a topological order, and if it cannot peel them all, the graph has a cycle.