Graphs are the default shape of everything

Trees, orders, dependencies, state machines and schedules are all graphs wearing different vocabularies. Learning the general object once beats learning five special cases.

A graph is a set of things and a set of pairs of those things. That is the entire definition, and its poverty is the point: almost any structure you meet in computing turns out to be a graph with extra adjectives, which means a result proved about graphs in general applies to all of them at once.

The adjectives#

Acyclic and connected — a tree. Every hierarchy, every parse, every filesystem.
Acyclic and directed — a DAG. Every build system, every dependency resolver, every migration order.
Directed with labelled edges — a state machine. Every protocol and every parser.
Bipartite — a matching problem. Every assignment of workers to shifts or shards to nodes.
Weighted — a shortest-path problem. Every routing table and every scheduler.

Notice how much of a working engineer's week is on that list. The value of naming the general object is that a technique learned in one row transfers to the others for free — topological order is the same idea whether you are ordering migrations or resolving imports.

If you find yourself inventing an algorithm for a bespoke structure, check first whether the structure is a graph with a different vocabulary. It usually is.

The two traversals#

Almost every graph algorithm is a traversal with bookkeeping attached, and there are only two traversals. The difference between them is one data structure.

def traverse(graph, start, frontier):
    seen = {start}
    frontier.add(start)
    while frontier:
        node = frontier.take()        # pop() -> DFS
        yield node                    # popleft() -> BFS
        for nxt in graph[node]:
            if nxt not in seen:
                seen.add(nxt)
                frontier.add(nxt)

The same eleven lines. A stack gives depth-first, a queue gives breadth-first, and every classical algorithm in this area is one of these two with something recorded on the way.

Record the depth and breadth-first search gives you shortest paths on an unweighted graph. Record finish times and depth-first search gives you a topological order and the strongly connected components. Record the predecessor and you get the path itself. The algorithms are not separate inventions; they are annotations on one loop.

What to take forward#

Two things. First, when a problem resists, ask what the vertices are and what the edges are — the question is frequently the whole solution. Second, resist the urge to write a custom traversal. The eleven lines above, plus whatever you record on the way, cover more ground than any special-purpose routine you are likely to write under time pressure.