Looking for algorithm finding euler path

Question

I'm looking for an algorithm to find an Euler path in a graph.

I've seen a good one a couple of weeks ago but I can't find it now, I remember there was tagging edges, something with even/odd connections...

Do you know a similar, simple and straightforward algorithm?

Answer 1

From Graph-Magics.com, for an undirected graph, this will give you the tour in reverse order, i.e. from the end vertex to the start vertex:

1. Start with an empty stack and an empty circuit (eulerian path).
   • If all vertices have even degree: choose any of them. This will be the current vertex.
   • If there are exactly 2 vertices having an odd degree: choose one of them. This will be the current vertex.
   • Otherwise no Euler circuit or path exists.

Repeat step 2 until the current vertex has no more neighbors and the stack is empty.

2. If current vertex has no neighbors:
   • Add it to circuit,
   • Remove the last vertex from the stack and set it as the current one.

Otherwise:

• Add the vertex to the stack,
• Take any of its neighbors, remove the edge between selected neighbor and that vertex, and set that neighbor as the current vertex.