desik's blog

Why does the Eulerian Tour Algorithm actually work?
By desik, history, 7 years ago, In English

I actually understood the method done in Euler Tour algorithm but don't understand why it works? Here is the pseudo.

dfs (v):
           for u in adj[v]:
               erase the edge v-u and dfs(u)
            push v at the end of e
  • Vote: I like it
  • +6
  • Vote: I do not like it

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

Before running this algorithm, you need to check whether a Euler tour actually exists (even degree for all vertices in connected undirected graph). Suppose you start at node v. Then for ALL other nodes, since degree is even, if you can "enter" that node by some edge, you can most definitely "exit" it too. Because for every incoming edge, there is some outgoing edge (as degree is even). So, the only way for your algorithm to terminate is at vertex v, i.e. when you've exhausted every edge in the graph.

This is the most intuitive explanation for me. :)

→ Reply