Graph algorithms

✋ Move — drag a vertex. On tabs with a start vertex, tapping a vertex makes it the start.

＋ Vertex — tap empty space to add a vertex (named A, B, C … or 0, 1, 2 …); tap a vertex to rename it.

／ Edge — drag from one vertex to another, or tap one and then the other.

# Weight — tap an edge to set its weight (negative weights are allowed); tap a vertex to give it a weight, which the topological-sort tab uses as a task duration.

✕ Erase — tap a vertex or an edge to delete it.

↶ Undo, ◯ Circle (lay the vertices out on a circle) and Clear; tick directed or weighted to change the kind of graph.

Draw & Euler — each vertex’s degree (in and out for a directed graph), the handshake lemma Σ deg = 2|E| side by side, connected components in different colours (and strongly connected components for a directed graph), and whether an Euler path or circuit exists, with the odd-degree vertices ringed in red. When one exists, stepping traces it edge by edge with Hierholzer’s algorithm. Simple graphs also get the planarity test E ≤ 3V − 6 (E ≤ 2V − 4 when triangle-free), which proves K₅ and K₃,₃ non-planar.

Matrix & walks — the adjacency matrix, linked to the drawing: hover a cell to find its edge, click it to add or remove the edge. Below it, Aʳ for r from 1 to 8; click a cell to list the walks it counts and trace one on the drawing.

BFS vs DFS — the two searches side by side from the same start, with the queue and the stack shown live, BFS distances and DFS discovery order on the vertices, and the route each finds to the exit. Maze mode swaps the graph for a 12 × 12 maze with a few loops: BFS floods outward in rings while DFS snakes down corridors. DFS here is the book’s recursive visit(), so its stack is the current path.

Shortest paths — Dijkstra, one move per finished vertex and one per relaxed edge, with the book’s trace table (step, finished vertex, then distance (parent) for every vertex); or Bellman–Ford, one move per edge relaxation with a row per pass, and a final check pass that finds negative cycles. Negative edge loads the book’s three-vertex example; whenever a weight is negative, Dijkstra’s answers are compared with the true distances and the wrong ones shown in red. rates (−ln) treats weights as exchange rates and uses −ln(rate), which turns the book’s arbitrage example into a negative cycle.

Topological sort — Kahn’s algorithm with ties taken alphabetically, as in the book: in-degrees on the vertices, the ready set, and the book’s table (take, in-degree changes, ready afterwards). If it gets stuck, the leftover vertices and a cycle among them are shown. Give the vertices weights (durations) and the critical-path table fills in alongside: earliest start and finish, latest finish and slack, with the critical path drawn in red.

Spanning trees — Kruskal, with the sorted edge list, the keep/skip table and the union–find forest (vertices coloured by the root of their component); or Prim from a start vertex, with the cheapest known link to each outside vertex.

Colouring — greedy colouring in an order you choose (as listed, alphabetical, largest degree first, DSatur, a typed order, or Shuffle), compared with the exact chromatic number found by search; or two-colouring by BFS, which either splits the graph into two sides or finds an odd cycle.

Tours — Hamiltonian cycles and the travelling salesman problem: brute force over every order of the other vertices (each cycle counted once, not once per direction; up to 9 vertices), showing the tour being checked and the best so far, against nearest neighbour, which is fast but can be badly wrong.

PageRank — power iteration on the Google matrix G = dM + (1 − d)/n·J, one iteration per step, next to a crowd of 2,000 random surfers who make one hop per step (follow a random link with probability d, otherwise teleport). Pages are sized by rank; the bar chart compares the exact vector with the share of surfers on each page, and a log plot shows the step size shrinking by about d per iteration. The damping slider runs from 0 to 1; untick dead ends teleport to let probability leak out of pages with no links (watch the total fall below 1 at d = 1).

Brute-force tours stop at 9 vertices (20,160 tours for an undirected graph); the matrix view at 14 vertices; the exact chromatic number at 22.

Spanning trees and colouring ignore arrow directions. Topological sort needs a directed graph.

PageRank treats an undirected edge as a link each way and counts parallel links once.

The surfers use a fixed random seed, so the same graph and d always give the same crowd.

Shortest paths use the cheapest of any parallel edges.