Implementation

This chapter implements BFS, DFS and Kahn's topological sort in Python on an adjacency list adj (a list of lists) whose vertices are numbered 0 to n-1. It then ports the same BFS to C++, Java and TypeScript.

BFS: shortest distances and path recovery

from collections import deque


def bfs(adj, start):
    n = len(adj)
    dist = [-1] * n          # -1 = not reached yet
    parent = [-1] * n
    dist[start] = 0
    queue = deque([start])
    while queue:
        u = queue.popleft()
        for v in adj[u]:
            if dist[v] == -1:            # first time we see v
                dist[v] = dist[u] + 1
                parent[v] = u
                queue.append(v)
    return dist, parent


def path_to(dist, parent, target):
    if dist[target] == -1:
        return None                      # unreachable
    path = []
    while target != -1:
        path.append(target)
        target = parent[target]
    return path[::-1]

• dist doubles as the visited marker: anything other than -1 has already been queued.
• deque.popleft() is O(1). list.pop(0) is O(n) and must not be used as a queue.
• Because vertices are marked on enqueue, each one enters the queue exactly once.
• path_to walks the parent pointers back from the target and reverses the result, returning None for unreachable vertices.

DFS: recursive, iterative, and components

def dfs_recursive(adj, start):
    seen = [False] * len(adj)
    order = []

    def visit(u):
        seen[u] = True
        order.append(u)
        for v in adj[u]:
            if not seen[v]:
                visit(v)

    visit(start)
    return order


def count_components(adj):
    comp = [-1] * len(adj)
    count = 0
    for s in range(len(adj)):
        if comp[s] != -1:
            continue
        comp[s] = count
        stack = [s]
        while stack:                     # iterative DFS
            u = stack.pop()
            for v in adj[u]:
                if comp[v] == -1:
                    comp[v] = count
                    stack.append(v)
        count += 1
    return count, comp

• The recursive version is short and readable, but it can hit Python's default recursion limit (about 1000). Use the iterative form for large graphs.
• count_components starts a new traversal from every vertex that has no label yet; each traversal paints one component. Only reachability matters here, not order, so a simple mark-on-push stack is enough.

Topological sort: Kahn and DFS

def topo_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 = cycle


WHITE, GRAY, BLACK = 0, 1, 2

def topo_dfs(adj):
    color = [WHITE] * len(adj)
    order = []

    def visit(u):
        color[u] = GRAY                  # in progress
        for v in adj[u]:
            if color[v] == GRAY:
                raise ValueError("cycle")  # back edge
            if color[v] == WHITE:
                visit(v)
        color[u] = BLACK                 # finished
        order.append(u)

    for u in range(len(adj)):
        if color[u] == WHITE:
            visit(u)
    return order[::-1]