Hierholzer's Algorithm

Hierholzer's algorithm finds an Eulerian circuit, a closed walk that traverses every edge of a connected graph exactly once, in a graph where every vertex has an even degree. It works by starting at an arbitrary vertex and following unused edges until returning to that same starting vertex, forming an initial closed trail, then checking whether any vertex on that trail still has unused edges; where one does, the algorithm splices in a new closed trail beginning and ending at that vertex, merging it into the growing circuit, and repeats this splicing process until no unused edges remain. Carl Hierholzer worked out the method before his early death in 1871, and Christian Wiener arranged for the complete proof and description to be published posthumously in 1873. Implemented with an appropriate edge-tracking data structure, the algorithm runs in linear time in the number of edges, which makes it more efficient in the worst case than the older Fleury's algorithm for the same problem.