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?
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.
Hi Satyaki3794, Can we use Hierholzer's Algorithm to find an Euler Path in a graph?
piyukr Yes you can ! Check my answer here : Math.StackExchange
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
Perhaps it is meant that it is advisable to consider loops separately
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.