Welcome, guest | Sign In | My Account | Store | Cart

Takes as input a graph and outputs Eulerian path (if such exists). The worst running time is O(E^2).

Python, 27 lines
 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27``` ```# Finding Eulerian path in undirected graph # Przemek Drochomirecki, Krakow, 5 Nov 2006 def eulerPath(graph): # counting the number of vertices with odd degree odd = [ x for x in graph.keys() if len(graph[x])&1 ] odd.append( graph.keys() ) if len(odd)>3: return None stack = [ odd ] path = [] # main algorithm while stack: v = stack[-1] if graph[v]: u = graph[v] stack.append(u) # deleting edge u-v del graph[u][ graph[u].index(v) ] del graph[v] else: path.append( stack.pop() ) return path ```

Example: (a well-known puzzle - how to draw an envelope without lifting a pen) eulerPath({ 1:[2,3], 2:[1,3,4,5], 3:[1,2,4,5], 4:[2,3,5], 5:[2,3,4] })

The worst time complexity can be easily changed into O(E) category. All you have to do is providing different graph representation which allows you deleting an edge in O(1) time.

#### 1 comment Karuppasamy 8 years, 6 months ago

We can find Complete eulerian path using HIERHOLZER’S Algorithm. Complete C code and explanation available in following link. http://iampandiyan.blogspot.in/2013/10/c-program-to-find-euler-path-or-euler.html Created by Przemek Drochomirecki on Sun, 5 Nov 2006 (PSF)

### Required Modules

• (none specified)