Hierholzer Algorithm to Find Eulerian Path
Prerequisites
Before reading this article, you should learn:
Summary in One Sentence
The Hierholzer algorithm is used to find Eulerian paths or Eulerian circuits. Its core idea is the reverse postorder result of DFS traversal of all edges in a graph.
In the article Eulerian Graph and One-Stroke Game, we learned the basic concepts of Eulerian graphs and discussed how to check if an Eulerian path or circuit exists.
The key is to look at the degree of nodes. Here is a simple summary. If you forget the reason, please review it first.
For undirected graphs:
If every node has an even degree, the start and end nodes are the same. There is an Eulerian circuit. You can start at any node, visit all edges, and return to the starting point in the end.
If there are exactly two nodes with odd degree, the start and end nodes are these two nodes. There is an Eulerian path. You can start from any of the odd-degree nodes, visit all edges, and end at the other odd-degree node.
For directed graphs:
If every node's in-degree equals its out-degree, the start and end nodes are the same. There is an Eulerian circuit. You can start at any node, visit all edges, and return to the starting point in the end.
If exactly two nodes have different in-degree and out-degree, the start and end nodes are these two nodes. There is an Eulerian path. You can start at any node with in-degree not equal to out-degree, visit all edges, and end at the other such node.
Now let's look at the code for the Hierholzer algorithm. It can find an Eulerian path or circuit in time.