Real-World Use

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.

Libraries and tools

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.