Space-Efficient Hierholzer

An Eulerian tour of an undirected multigraph, written out in traversal order using only O(n) words of working memory instead of O(m). A sparse spanning circuit — the skeleton S — is computed first and then walked step by step; along the way the remaining edges are processed in batches, and every batch leaves behind nothing but a forest. Reads the Algs4 Graph format (V, then E, then the edges).

Graph

Start

Variant

Delay 900ms

Random V E

Step 0 / 0

Status

Press Step or Play to begin.

Graph

edge of G

spanning tree T

skeleton S, not yet written

skeleton S, written out

forest from the Forest Lemma (P, F_i)

batch N_i … N_j

circuits C_k, one tone each (earlier = lighter)

G_i

vertex

revisit copy

Output stream append-only — click to jump there, hover to light it up

Solid = already written. Outlined skeleton = the rest of the roadmap, already known; dashed ⟨C_k⟩ = a detour still to be computed.

Drawing

expanded skeleton (revisits drawn as marked copies) collapse parallel edges into one with a counter show G_i arrows on the written tour walk a token along each newly written piece

Algorithm

Invariant (1)

—

C₁ + ⋯ + C_i + F_i = G_i, checked at every round boundary

Cost

Edit / paste a graph

Format (Sedgewick & Wayne Graph): first line is the number of vertices V, second line the number of edges E, then E lines each holding an undirected edge v w. Vertices are 0 … V−1. Parallel edges and self-loops are allowed.

Optional fixed layout: after the edges, add exactly V more lines of x y — one pair per vertex, in order — to pin down the drawing of the input graph. Once the skeleton is computed the vertices are rearranged by first appearance on it, so these coordinates only affect the setup phase.

Generate (top right) builds a random Eulerian multigraph with the requested number of vertices and edges — a random Hamiltonian cycle with random circuits piled on top, which keeps every degree even — and drops the result into this box, so you can keep or edit it.

The graph must be Eulerian: connected, with no isolated vertices, and every degree even (a loop counts twice). Anything else is rejected with a message here.