Algorithms & Data Structures
the bound is a claim, and it is checkable
Concept

Topological sort — where it appears

An ordering of a directed acyclic graph's vertices in which every arc runs forwards. It costs two passes over the arcs to produce, it exists only when the graph has no cycle, and it is the order a priority queue would otherwise have to discover.

Named by 3 essays across one field — each of them below, with the objects they name alongside it.

10010³10³10⁴10⁵10⁶10⁷Vcounted workTopological order, one passDijkstra, binary heapBellman–Ford, all passesV from 64 to 2048, directed, acyclicwork = scans + visits + relaxations + queue comparisons

The precondition that removes the queue

Dijkstra maintains a priority queue to discover which vertex is safe to finalise next, and on a directed acyclic graph 65% of its counted work goes into that queue. The order it is discovering is already known. Relaxing in topological order makes exactly one relaxation per arc — 1,536 arcs, 1,536 relaxations — with no queue at all, and negative weights are fine.

graphs · Graph adjacency scansrelaxationsqueue comparisonsvisitsKosaraju, two passes5,632Tarjan, one pass2,560V = 1024, E = 1,536, directed, components plantedevery segment counted exactly

Two passes or one, and what the second one costs

Kosaraju's algorithm and Tarjan's find the same strongly connected components of the same graph, in the same class, and one of them examines three times as many arcs as the other. The extra pass everybody counts is not where the difference is — building the reversed graph is, and no statement of "two depth-first passes" mentions it.

graphs · Graph 24816326410⁵10⁶components the graph is built fromcounted workcomponents firstBellman–Ford, early exitBellman–Ford, every passV = 1,024, negative arcs between componentsvertices relabelled at random

A graph is as hard as its largest cycle

Negative arcs rule out Dijkstra's algorithm and leave Bellman–Ford, which on a thousand vertices does three million units of work. Stopping it when a pass changes nothing brings that to 78,496. Finding the strongly connected components first and running it inside each one brings it to 38,549 — and to a quarter of the early-exit cost when the components are small, because every cycle lives inside one.

graphs · Graph

Named alongside it

The objects these essays reach for when they reach for this one.

Counted primitiveBellman–FordCondensationDirected acyclic graphDirected graphNegative weightRelaxationShortest pathStrongly connected componentsComplexity classDepth-first searchDijkstra's algorithm

All concepts