Counting on a graph

Every measurement on this site so far has gone through an instrumented array whose four primitives — read, write, compare, swap — tally exactly. That instrument is the reason a caption here can quote a number instead of a feeling, and it does not generalise to a graph at all.

Not “generalises badly”. Does not generalise. A breadth-first search over a graph held as adjacency lists performs no comparisons whatsoever, and if it is counted with the array’s instrument the answer is zero. The instrument is not measuring the wrong thing; it is measuring a thing that is not happening.

So the field needs its own primitives, and choosing them is the work.

Three operations, and why those three #

A graph algorithm spends its life doing three things, and each of them is the term that puts one of the two size parameters into the bound.

Scanning an adjacency. Asking a vertex which vertices it is joined to. Charged one unit per edge slot examined — so a vertex of degree seven costs seven, and a vertex of degree zero costs nothing. Summed over a traversal that visits everything, this is where the $E$ in every graph bound comes from.

Reaching a vertex for the first time. Charged once, and only once: calling visit on a vertex already seen returns false and costs nothing, so an algorithm cannot inflate its own count by asking twice. This is where the $V$ comes from.

Relaxing an edge. Attempting to improve a tentative distance — comparing what is known about a vertex against a route through one of its neighbours. Charged whether or not it improves anything, because the work is in the attempt. Dijkstra and Bellman–Ford are, in a real sense, nothing but sequences of relaxations.

And then a fourth quantity, counted separately rather than mixed in:

Priority-queue operations. Pushes, pops, decrease-keys, and the comparisons performed inside the queue. Kept apart because which queue an implementation uses decides its complexity class, the choice is invisible in every published pseudocode, and folding the queue’s work into the traversal’s would hide the one decision that matters most.

The unit, stated because it is a choice #

These figures report a quantity called work: the four counts, summed. One edge slot examined, one vertex reached, one relaxation attempted and one queue comparison each count as one.

That is a cost model rather than a fact, and it is exactly the same kind of choice as charging one unit per comparison in the sorting field. A relaxation involves an addition and a comparison; an adjacency scan is a pointer dereference; a queue comparison is a comparison. They are not the same amount of machine. Summing them is defensible for comparing algorithms and indefensible as a prediction of anything, and both halves of that are printed on every figure that uses it.

The components are always kept separately, so any figure that wants one of them alone can have it — and two of them do, because the interesting story is usually about which component dominates rather than about the total.

The check that makes the counts mean anything #

The sorting field’s central safeguard is that a sort which does not sort is not measured, it is an error, because a broken algorithm’s counts still plot a perfectly convincing curve. The graph field needs the same thing and the check is different in each case.

A traversal must reach every vertex of a connected graph. All the input graphs here are built connected — a random spanning tree first, then the extra edges — so a traversal that visits 2,047 of 2,048 has a bug, and a bug that would otherwise produce a beautifully linear curve.

Two shortest-path algorithms that share no code must agree. Dijkstra with a heap, Dijkstra with an array queue, and Bellman–Ford compute the same distances by three different routes. Requiring all three to agree at every vertex is a much stronger check than any of them passing a test alone, and it is the graph analogue of computing the sorting floor twice.

Prim and Kruskal must find trees of the same weight. Not the same tree — ties break differently — but the same total, because a minimum is a minimum. Two algorithms with nothing in common agreeing on a number is the strongest evidence available here.

And, as everywhere on this site, the checks are themselves checked: the gate hands the framework a traversal that deliberately stops one vertex early and requires it to be caught.

The first result: BFS and DFS are the same algorithm #

With the instrument built, the most basic question in the field has an answer that is slightly startling.

Breadth-first and depth-first search over the same graph perform exactly the same counted work. Not approximately: identically. On a 2,070-vertex grid both examine 8,098 edge slots and both reach 2,070 vertices. On a random graph of 2,048 vertices and 6,144 edges both examine 12,288 slots and reach 2,048. Every counter this site has for measuring time reports them as indistinguishable, and it is right to.

They visit in wildly different orders, and the order does not cost anything.

What differs is how many vertices each has to hold at once. On that grid, breadth-first search’s queue peaks at 45 vertices and depth-first’s stack peaks at 1,012 — a factor of twenty-two, on the same graph, doing the same work.

That is a difference in space, and until this phase the site had no instrument for it either. It has one now, and the BFS-against-DFS comparison is the cleanest case for it in the whole collection: two algorithms that a complete accounting of time cannot separate, separated entirely by what they keep.

It is also worth noticing that the factor of twenty-two is a property of the graph, not of the algorithms. On a random sparse graph of the same size the two frontiers are 1,102 and 1,117 — indistinguishable. A random graph has a diameter of about $\log V$, so depth-first search cannot get deep, and it has an enormous middle layer, so breadth-first search cannot stay narrow. The grid has the opposite shape in both respects. The received advice that “BFS uses more memory than DFS” is true on a grid, false on a random graph, and stated about neither.

What the counts do not separate, and what that is good for #

There is a temptation, having built an instrument, to use it on everything and report the differences. The more useful result here is a non-difference, and it took the instrument to establish it.

Three claims of the form “X is faster than Y” collapse under counting:

• BFS against DFS: identical, as above.
• Recursive DFS against the explicit-stack version: identical in every array count and in every graph count. The difference is that one of them uses the call stack and the other uses a heap-allocated one, which is a space and reliability question rather than a speed one.
• Topological sort against a plain traversal: within a small constant. Kahn’s algorithm on the graphs here does about twice the adjacency scanning, because it counts in-degrees in a first pass and then decrements them in a second, and that is the entire cost of getting an ordering rather than a set.

A field whose first three findings are “these are the same” is a field with an instrument worth trusting. Instruments that only ever find differences are usually finding their own noise.

Which of the two terms is the large one #

A graph bound is a sum of a term in $V$ and a term in $E$, and the notation gives them equal billing. Measured, they are almost never comparable, and which of them dominates is decided by the graph rather than by the algorithm.

Breadth-first search, the same code, on the three families:

The scan count is always $2E$ — every undirected edge is walked from both ends — and the visit count is always $V$. So the ratio is simply the average degree, and it runs from four to two hundred and fifty-nine over these three families.

Two consequences follow, and both are things a bound in $V + E$ obscures rather than states.

On a dense graph the $V$ term is noise. It is 0.4% of the work at density 0.5. Any optimisation of per-vertex bookkeeping — a cheaper visited-set, a smaller distance array, a better queue — is optimising a term that is four parts in a thousand. This is the same observation that takes Dijkstra’s queue apart, reached before any algorithm more complicated than a traversal is involved.

On a planar graph the two terms are within a factor of four. A grid has degree four by construction, and real planar-ish graphs — road networks, meshes, circuit layouts — are in the same range. For those, $V$ and $E$ are genuinely the same order and the sum in the bound is doing what the notation suggests.

So $O(V + E)$ describes a family of situations spanning two orders of magnitude in which term matters, and the expression is identical across all of them. That is not a criticism of the bound, which is correct and tight; it is a statement about how much of the useful information a correct, tight bound can fail to carry.

The site’s response is procedural and small: every graph figure prints $V$ and $E$ in its caption strip, and the component figure exists so that the split can be seen rather than reasoned about.

Two representations, one graph #

There is a second design decision inside the counted graph, and it turns out to carry an entire essay.

An adjacency structure can be held two ways. As lists: each vertex owns a list of edge records, allocated whenever the edge was created, scattered through memory in creation order. Or as CSR — compressed sparse row — a single flat array of every edge, sorted by source vertex, with an index saying where each vertex’s block begins.

Both are implemented here and both are counted identically, which is asserted rather than assumed: the gate requires the two to report the same number of edge scans, the same number of visits and the same trace length, and to differ in nothing except the addresses. If they ever diverged in counted work, any comparison between them would be comparing two different traversals.

What differs is only where the edges live, and that is enough to feed the cache model two very different traces from one traversal.

This is the two-counts theme at the widest gap it reaches anywhere on this site. No pair of sorting algorithms manages a factor of three and a half in modelled misses while agreeing exactly on the operation count, because sorting algorithms that agree on the operation count are usually doing nearly the same thing. Here the operations are not merely equal in number, they are the same operations in the same order, and only the addresses differ. The essay on the two layouts is about what follows from that.

The same sweep, four ways #

One sweep on one regime is a picture of one regime, and the whole point of counting rather than quoting is that the counts can be taken again wherever the reader doubts them.

That is the first thing a sweep can settle and a table cannot: which distinctions the regime itself erases. Narrowing the set of algorithms settles the second.

The last of the four is the one an implementer is actually choosing between, and it is worth putting on the dense regime because that is where a real graph usually sits.

Where the graphs come from #

Every graph here is generated from a stated seed, like every array on the site, and for the same reason: a figure built on Math.random() shows different numbers on every build and its caption is quoting numbers the reader’s copy does not contain.

Four families, and each exists because it answers a different question.

Sparse — a random graph at a fixed average degree, built by laying down a random spanning tree first and then adding edges until the target is met. Connected by construction, so every traversal measurement is over the whole graph. This is the family for sweeping $V$ with $E$ proportional to it.

Dense — every possible edge included with a stated probability. $E$ grows like $V^2$, and the fitted classes come out different on this family than on the last one, which is the whole reason both exist.

Grid — a square lattice. Planar, degree four, diameter $\sqrt{V}$: the shape most real graphs of interest are nearer to than they are to a random one, and the family on which several published bounds stop describing what happens.

Path — the degenerate case, and the worst case for a depth-first stack.

Naming the family is not decoration. A graph bound with no stated density is a bound with a free variable in it, and the next essay is about how much damage that does.

The primitive that is missing #

Four counters cover what a traversal does, and there is a fifth operation that graph code performs constantly and that none of them charges for: asking whether a particular pair of vertices is joined.

It is absent here because no algorithm in this field performs it. Traversals and shortest-path algorithms enumerate a vertex’s neighbours; they never ask about a specific one. But a great many graph problems do — triangle counting, subgraph matching, clustering coefficients, anything that tests a candidate edge rather than following an existing one — and for those the operation is the dominant cost.

It is also the operation on which the two representations differ most starkly, and in the opposite direction from the sweep result. An adjacency matrix answers it in one read. An adjacency list answers it by scanning the vertex’s neighbours, which is the degree — so the same question costs one unit on a structure of $\Theta(V^2)$ bits and up to $V$ units on one of $\Theta(V+E)$.

That is a genuine space-for-time trade with no dominant side, and it is the reason adjacency matrices survive at all on graphs small enough for $V^2$ to be affordable. Nothing in this field measures it, so nothing here says where the crossing is; the counter would be a fifth primitive and the algorithms that need it are a phase this collection has not written.

And the one that is counted is charged twice #

One detail of the adjacency count is worth stating because every number in this field depends on it.

The graphs here are undirected, and an undirected edge appears in the adjacency structures of both its endpoints. So a traversal that examines every edge examines $2E$ slots, which is why the scan counts in the table above are exactly twice the edge counts.

On a directed graph the same traversal examines $E$ slots, because each edge is stored once. So a scan count is not comparable across directedness without dividing by the right factor, and a benchmark comparing an undirected traversal against a directed one is reporting a factor of two that is entirely about the representation.

The convention here is to count slots rather than edges, because a slot is what the algorithm actually touches and because the memory-layout results in this field are about slots. The caption strip prints $V$ and $E$, and the factor between $E$ and the scan count is the thing a reader has to supply — which is stated here once so that it does not have to be repeated on every plate.

What this field is for #

The foundation of this site measured one-dimensional arrays for time. A reader could reasonably have concluded that the method only works when the structure is that simple, and that conclusion would have been wrong in two separate ways.

Graphs are the first correction. The cost has two parameters instead of one, so the fit needs a second variable and a stated regime; the structures are pointers rather than indices, so the memory model has something much larger to say; and the field contains at least one bound — union–find’s — whose relationship between the formal class and the practical constant is the exact inverse of everything in the foundation.

Space is the second correction, and the two arrive together on purpose. An adjacency matrix costs $\Theta(V^2)$ memory and answers “is there an edge?” in constant time; an adjacency list costs $\Theta(V + E)$ and answers it in time proportional to the degree. That is a space-against-time trade with no dominant answer, at a scale where it decides whether the problem fits in memory at all — which is the growth-factor argument again, several orders of magnitude further up.

The instrument in this essay is the smallest part of all that. It is four counters and a check that the traversal finished. What it buys is the right to say a number.