Eulerian Path and Circuit Algorithm - How does it work?

Question

I have found several versions of algorithms the find a Eulerian path/circuit in a graph, but I'm having trouble understanding why they work. For example http://www.graph-magics.com/articles/euler.php gives a clear description of the steps, but I can't see how those steps work, and certainly don't imagine I could have come up with the algorithm myself.

What insights/intuition would be needed to be able to develop this algorithm for oneself?

From my reading, it seems the basic idea is to find multiple circuits and somehow "splice" them together. However, the details are very murky in my mind and I'd like to understand in detail, including why and when you can do this etc.

Does the algorithm given in the link have a name? Is it based on DFS? Is it a version of Fleury’S Algorithm? If not how does it differ? (It seems Fleury's Algorithm makes decisions which the one in the article doesn't, but I may well be mistaken.)

It may well be that there are multiple algorithms for this problem, in which case it would be good to know which the one in the article is, and what the alternatives are.

It would also be very helpful to have some pseudocode for the algorithm in the article, based off an adjacency list, if anyone is willing to provide one.

Answer 1

The algorithm you linked is (or is closely related to) Hierholzer's algorithm. While Fleury's algorithm stops to make sure no one is left out of the path (the "making decisions" part that you mentioned), Hierholzer's algorithm zooms around collecting edges until it runs out of options, then goes back and adds missing cycles back into its path retroactively.

I'm not entirely clear how Hierholzer did this originally, but I agree with you that the version linked is using a depth first search approach to the problem, then backing up to the last "choice" to pick up the missing cycles. (This is why I'm not sure if it is Hierholzer's algorithm, or just related.)

In your link, it provides a "sample execution" which is far more detailed than any pseudo-code I would be able to provide you, but this site (geeksforgeeks) has C++ and Python code for Hierholzer's algorithm.