Graph traversal is not just an interview topic. Build tools, package managers, garbage collectors, web crawlers and the paint-bucket tool in an image editor all run on the BFS, DFS and topological sorting covered in this guide. This chapter looks at real systems, standard libraries and common mistakes.
Where traversal shows up
- Build systems and task runners: Make, Bazel, Gradle and CI pipelines model task dependencies as a DAG and run tasks in topological order. Tasks with in-degree 0 can run at the same time, which is what makes parallel builds possible.
- Package managers: npm, pip and Cargo walk the dependency graph to decide installation order and report circular dependencies.
- Garbage collectors: mark-and-sweep collectors traverse references from the roots (globals, stack frames), mark every reachable object, and reclaim the rest.
- Web crawlers: starting from seed pages, a crawler expands links breadth-first, using a depth limit and a visited set so it never fetches a page twice.
- Flood fill: the paint-bucket tool finds the connected region of same-colored pixels with a grid BFS or DFS.
- Spreadsheets: cell formulas form a dependency graph; a topological order decides recalculation order, and a cycle is reported as a circular reference.
- Deadlock detection: databases build a wait-for graph of which transaction waits on which lock; a cycle means deadlock.
Since Python 3.9 the standard library ships a topological sorter in graphlib. Each dictionary value lists a node's predecessors, the things that must come first.
from graphlib import TopologicalSorter, CycleError
deps = {"app": {"ui", "net"}, "ui": {"core"}, "net": {"core"}}
print(list(TopologicalSorter(deps).static_order()))
# e.g. ['core', 'ui', 'net', 'app'] (order within a level is not guaranteed)
try:
list(TopologicalSorter({"a": {"b"}, "b": {"a"}}).static_order())
except CycleError as error:
print("cycle:", error.args[1])
TopologicalSorter also supports parallel execution through prepare(), get_ready() and done(), handing ready tasks to workers as their prerequisites finish. For heavier graph work, NetworkX provides BFS, DFS, components and topological sorting out of the box.
import networkx as nx
grid = nx.grid_2d_graph(3, 3) # a 3 x 3 grid graph
print(nx.shortest_path_length(grid, (0, 0), (2, 2))) # 4, BFS when unweighted
print(nx.number_connected_components(nx.Graph([(0, 1), (2, 3)]))) # 2
print(list(nx.topological_sort(nx.DiGraph([("core", "ui"), ("ui", "app")]))))
The mark phase of a garbage collector is an iterative DFS in disguise.
def mark(roots, refs):
live, stack = set(), list(roots)
while stack:
obj = stack.pop()
if obj in live:
continue
live.add(obj)
stack.extend(refs.get(obj, []))
return live
refs = {"main": ["a"], "a": ["b"], "b": ["a"], "c": ["d"]}
print(mark(["main"], refs)) # {'main', 'a', 'b'}: c and d get collected
The cycle between a and b does not cause an infinite loop because of the visited set, and c and d are collected because nothing reachable points to them, regardless of their reference counts.
Common mistakes
- Marking too late: marking on dequeue in BFS lets one vertex be queued many times, wasting memory and time. Mark on enqueue.
- A list as a queue:
list.pop(0) in Python and shift() in JavaScript are O(n). - Recursion depth: recursive DFS overflows the stack on long chains with tens of thousands of vertices.
- Cycle checks in directed graphs: reaching an already visited vertex is not a cycle; reaching an in-progress (GRAY) one is. In undirected graphs, do not mistake the edge back to the immediate parent for a cycle.
- Unbounded implicit graphs: crawlers and state-space searches can be infinite, so always cap depth or count.
- Unreachable vertices: check for a distance of
-1 before using it in arithmetic.
Summary
Wherever there are dependencies there is a topological sort, and wherever there is a reachability question there is a BFS or DFS. In production, reach for proven implementations like graphlib or NetworkX first; when you write your own, double-check when you mark vertices, which queue you use, how deep you recurse, and how you define a cycle.
Further reading
0 comments
Sign in · Sign in to leave a comment.