Being a postman, you would like to know the best route to distribute your letters without visiting a street twice? This problem of finding a cycle that visits every edge of a graph only once is called the Eulerian cycle problem. It is named after the mathematician Leonhard Euler, who solved the famous Seven Bridges of Königsberg problem in 1736.

Hierholzer's algorithm, which will be presented in this applet, finds an Eulerian tour in graphs that do contain one.

Second cycle (green) and complete Eulerian cycle (a - c - e - f - c - d - b - a)

Computing Eulerian cycles

The problem of finden Eulerian cycles was first discussed in the 18. century. In the city of Königsberg (Kaliningrad nowadays) there existed exactly seven bridges, and people wondered whether one could find a cycle or at least a tour that would cross each bridge exactly once. The same problem occurs with the "Haus vom Nikolaus", which asks for drawing a house without lifting the pencil.

In Mathematics, one uses the concept of graphs and calls the corresponding structure Eulerian cycles, named after Leonard Euler. One asks for a list of edges such that every edge of the graph appears exactly once in the list. If you end at the same node that you started, it is called an Eulerian cycle, otherwise an Eulerian path.

Eulerian graphs

Leonard Euler was able to determine the exact conditions for a graph to contain an Eulerian cycle or tour. Hereby, one has to distinguish between directed and undirected graphs:

Undirected graphs
An undirected graph contains at least one Eulerian cycle if all of its nodes have an even degree. This means that all nodes have to be connected by two, four, six, ... edges to other nodes. This becomes obvious by the following argument: For all nodes you need exactly two edges, one to reach it and one to leave it. If we visit the node more than once, we would consequently need a multiple. A graph that has this property is called Eulerian graph.

For an Eulerian path one can relax the above requirements. Exactly two nodes then have to have an odd degree. For both of these nodes, one edge remains at the end; therefore one has to leave one of them one more time and arrive at the other one more time. These two nodes will then be the start and end node of the Eulerian path. Such a graph is called semi-Eulerian.

Directed graphs
For directed graphs the requirements mentioned above still hold, one just has to furthermore distinguish incoming and outgoing edges. To do so, a node's degree is separated into its indegree and its outdegree. The indegree describes the number of incoming edges, while the outdegree yields the number of outgoing edges. In order for a directed graph to be Eulerian, besides the degree being even the indegree of each node has to equal its outdegree.

For semi-Eulerian graphs one additionally requires a start node with an extra outgoing edge and an end node with an extra incoming edge.

When returning to the bridges of Königsberg, we conclude that the corresponding graph has four nodes with odd degree (red), therefore no Eulerian cycle exists. However, if the graph fulfilled all requirements, Hierholzer's Algorithm would compute an Eulerian cycle or path.

Idea of the algorithm

The basic idea of Hierholzer's algorithm is the stepwise construction of the Eulerian cycle by connecting dijunctive circles. It starts with a random node and then follows an arbitrary unvisited edge to a neighbour. This step is repeated until one returns to the starting node. This yields a first circle in the graph. If this circle covers all nodes it is an Eulerian cycle and the algorithm is finished. Otherwise, one chooses another node among the cycles' nodes with unvisited edges and constructs another circle, called subtour. By choice of edges in the construction the new circle does not contain any edge of the first circle, both are disjunct. However, both circles must intersect in at least one node by choice of the starting node of the second circle. Therefore one can represent both circles as one new circle. To do so, one iterates the nodes of the first circle and replaces the subtour's starting node by the complete node sequence of the subtour. Thus, one inegrates additional circles into the first circle. If the extended cycle does include all edges the algorithm is finished. Otherwise, we can find another cycle to include.

In the case of an undirected, semi-Eulerian graph the algorithm starts with one of the two nodes with odd degree. In the directed case with the node with one additional outgoing edge. One of the subtours to be found will then not form a cycle, instead it will also be a path. When integrating this "subtour" into the circle one has to make sure that start and end node of this path also form start and end of the complete Eulerian path.

What now?

h1>

Create a graph and play through the algorithm

Test your knowledge in the exercises

^{1} By Bogdan Giuşcă under GNU Free Documentation License 1.2, cf. Wikimedia.

Input: Undirected graph G=(V,E), no or exactly two nodes have odd degree
Output: List of nodes in Eulerian cycle/path

BEGIN
IF graph infeasible THEN END
IF graph semi-Eulerian THEN
start ← node with odd degree
ELSE
start ← arbitrary node
subtour ← ∅
tour ← {start}
REPEAT
start ← node in tour with unvisited edge
subtour ← {start}
current = start
DO
{current, u} ← take unvisited edge leaving current
subtour ← subtour ∪ {u}
current ← u
WHILE start ≠ current
Integrate subtour in tour
UNTIL tour is Eulerian cycle/path
END

How fast is the algorithm?

Speed of the algorithms

The
Speed of an algorithm is the total number of individual steps which are performed during the execution. These steps are for example:

Assignments – Set distance of a node to 20.

Comparisons – Is 20 greater than 23?

Comparison and assignment – If 20 is greater than 15, set variable
n
to 20

Simple Arithmetic Operations – What is 5 + 5?

Since it can be very difficult to count all individual steps, it is desirable to only count the approximate magnitude of the number of steps. This is also called the running time of an algorithm. Particularly, it is intersting to know the running time of an algorithm based on the size of the input (in this case the number of the vertices and the edges of the graph).

Running time of Hierholzer's algorithm

We assume we have a graph \(G = (V, E)\) with \(|V| = n\) and \(|E| = m\). In the first step, the algorithm computes a first circle \(T\). For the next subtour, the algorithm needs to find a nodes in \(T\) still having unvisited edges. This node will be the start for the following subtour which will be integrated in the first circle. Starting with an empty initial circle, the tour may at most be extended by n nodes. After each completed subtour, a new start node for the following subtour is searched. Looking fur unvisited edges, we have to look at m edges in the worst case. Therefore, the algorithm's running time is \(O(n*m)\).

We can optimize the algorithm by saving a seaparte adjacency list, from which visited edges are removed. Hence, when looking for unvisited edges in a node not all edges have to be checked. Instead, each edge is only checked one. Thus, a linear running time of \(O(n+m)\) is possible.

The same running linear time is necessary to check whether the graph is Eulerian, i.e. whether Hierholzer's algorithm may be used at all.

Where can I find more information about graph algorithms?

Other graph algorithms are explained on the Website of Chair M9 of the TU München.

A last remark about this page's goal and citations

Chair M9 of Technische Universität München does research in the fields of discrete mathematics, applied geometry and the optimization of mathematical problems. The algorithms presented on the pages at hand are very basic examples for methods of discrete mathematics (the research conducted daily at the chair reaches far beyond that point). This page shall provide the possibility pupils and students to understand and fully comprehend the algorithms (which are of importance also in daily life).

To cite this page, please use the following information:

Title: Hierholzer's Algorithm

Authors: Mark J. Becker, Wolfgang F. Riedl; Technische Universität München