Hierholzer's Algorithm

Graph Theory · Axiom Academy

An efficient algorithm for finding Eulerian circuits in graphs 1. Initial Walk: Start Anywhere, Walk Until Stuck Begin at any vertex and follow edges, marking them as used. Since all vertices have even degree, you're guaranteed to return to your starting vertex. This forms your initial circuit. Walk along unused edges, marking them as used Continue until you return to v (forming a circuit) After forming the initial circuit, examine each vertex on the circuit. If a vertex has unused edges, we can extend our tour by creating a new circuit starting from that vertex. Find a vertex with unused incident edges If found, start a new walk from this vertex If no unused edges remain, the circuit is complete When you find a vertex on the existing circuit with unused edges, perform another walk from that vertex. This creates a sub-circuit. Splice this new circuit into the main circuit at the common vertex. Start at vertex v with unused edges Form a new circuit using unused edges Insert this circuit into the main tour at vertex v Repeat until all edges are used Hierholzer's algorithm is remarkably efficient. Each edge is visited exactly once during the walks, and the circuit splicing operations can be performed efficiently using appropriate data structures. Each edge is traversed exactly once Using adjacency lists, finding next unused edge is O(1) amortized Circuit splicing with linked lists or stacks is O(1) per splice

This is the written version of the interactive lesson above. See the full Graph Theory course.