Takes as input a graph and outputs Eulerian path (if such exists). The worst running time is O(E^2).
Python, 27 lines
Download
Copy to clipboard1 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()[0] )
if len(odd)>3:
return None
stack = [ odd[0] ]
path = []
# main algorithm
while stack:
v = stack[-1]
if graph[v]:
u = graph[v][0]
stack.append(u)
# deleting edge u-v
del graph[u][ graph[u].index(v) ]
del graph[v][0]
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.
Tags: algorithms
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