hiddentesla's blog

Algorithm on euler circuits
By hiddentesla, history, 7 years ago, In English

so im learning Euler circuit now, and i found this algorithm

'tour' is a stack

find_tour(u):
	for each edge e=(u,v) in E:
		remove e from E
		find_tour(v)
	prepend u to tour

to find the tour, clear stack 'tour' and call find_tour(u),
where u is any vertex with a non-zero degree.

source: http://www.algorithmist.com/index.php/Euler_tour

i coded it, and got AC in an euler circuit problem (the problem guarantees that there is an euler circuit) however, i noticed that in the bottom of the algorithm, it says [WARNING! There is some error in this pseudo-code. The algorithm is not correct!]

does this mean that the algo has a high chance to print euler circuit? or something else?

  • Vote: I like it
  • +8
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
7 years ago, # |
← Rev. 2   Vote: I like it +5 Vote: I do not like it

I think this is Hierholzer's algorithm. Before applying it, you need to check that a Euler circuit actually exists for the given graph. Here is another good resource. Take a look at this problem which asks you to construct a Eulerian circuit. My code for the same can be found here.

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Hi Satyaki3794, Can we use Hierholzer's Algorithm to find an Euler Path in a graph?

    → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Hi, I know it's an old post, but could you please explain why you chose 62 for hashing?

    Edit: NVM, figured it out. It's because the password can have uppercase/lowercase letters and digits

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Perhaps it is meant that it is advisable to consider loops separately

→ Reply
»
3 years ago, # |
  Vote: I like it +7 Vote: I do not like it

i was really confused on how this is equivalent to Hierholzer's algorithm, as the pseudo-code you wrote looks nothing like that at all. This is also the code present in CP algorithms. So I came up with a proof:

Proof that this algorithm is equivalent to Hierholzer's:

Claim: For an Eulerian graph [graph which is connected and each vertex has even degree] of size $$$n$$$, $$$findTour(v)$$$ outputs a euler tour starting and ending at any arbitrary vertex $$$v$$$.

We can prove this claim by strong induction on $$$n$$$. Consider for a graph of size $$$k$$$. Let's start $$$findTour(v)$$$ on any arbitrary vertex $$$v$$$. Since each vertex has even number of edges, we will never get "stuck" on any vertex, since once we enter a vertex, we can exit it also. Consider when the recursion comes back to $$$v$$$ for the first time. It has deleted all edges from the graph which forms a simple cycle consisting $$$v$$$.

This means that the graph is now divided into smaller Eulerian graphs, with each vertex of the cycle being part of one such smaller eulerian graph. By induction, $$$findTour()$$$ on these vertices returns an eulerian circuit starting and ending at these vertices. So we combine the path in the stack, thus finding the euler tour.

→ Reply