### hiddentesla's blog

By hiddentesla, history, 7 years ago,

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.


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?

• +8

| Write comment?
 » 7 years ago, # | ← Rev. 2 →   +5 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.
•  » » 7 years ago, # ^ |   0 Hi Satyaki3794, Can we use Hierholzer's Algorithm to find an Euler Path in a graph?
•  » » » 7 years ago, # ^ | ← Rev. 2 →   0 piyukr Yes you can ! Check my answer here : Math.StackExchange
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 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
 » 5 years ago, # |   0 Perhaps it is meant that it is advisable to consider loops separately
 » 3 years ago, # |   +7 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.