Eulerian Path is a path in graph that visits every edge exactly once. Eulerian Circuit is an Eulerian Path which starts and ends on the same vertex.
We strongly recommend to first read the following post on Euler Path and Circuit.
http://www.geeksforgeeks.org/eulerian-path-and-circuit/
In the above mentioned post, we discussed the problem of finding out whether a given graph is Eulerian or not. In this post, an algorithm to print Eulerian trail or circuit is discussed.
Following is Fleury’s Algorithm for printing Eulerian trail or cycle (Source Ref1).
1. Make sure the graph has either 0 or 2 odd vertices.
2. If there are 0 odd vertices, start anywhere. If there are 2 odd vertices, start at one of them.
3. Follow edges one at a time. If you have a choice between a bridge and a non-bridge, always choose the non-bridge.
4. Stop when you run out of edges.
The idea is, “don’t burn bridges“ so that we can come back to a vertex and traverse remaining edges. For example let us consider the following graph.
There are two vertices with odd degree, ‘2’ and ‘3’, we can start path from any of them. Let us start tour from vertex ‘2’.
There are three edges going out from vertex ‘2’, which one to pick? We don’t pick the edge ‘2-3’ because that is a bridge (we won’t be able to come back to ‘3’). We can pick any of the remaining two edge. Let us say we pick ‘2-0’. We remove this edge and move to vertex ‘0’.
There is only one edge from vertex ‘0’, so we pick it, remove it and move to vertex ‘1’. Euler tour becomes ‘2-0 0-1’.
There is only one edge from vertex ‘1’, so we pick it, remove it and move to vertex ‘2’. Euler tour becomes ‘2-0 0-1 1-2’
Again there is only one edge from vertex 2, so we pick it, remove it and move to vertex 3. Euler tour becomes ‘2-0 0-1 1-2 2-3’
There are no more edges left, so we stop here. Final tour is ‘2-0 0-1 1-2 2-3’.
See this for and this fore more examples.
Following is C++ implementation of above algorithm. In the following code, it is assumed that the given graph has an Eulerian trail or Circuit. The main focus is to print an Eulerian trail or circuit. We can use isEulerian() to first check whether there is an Eulerian Trail or Circuit in the given graph.
We first find the starting point which must be an odd vertex (if there are odd vertices) and store it in variable ‘u’. If there are zero odd vertices, we start from vertex ‘0’. We call printEulerUtil() to print Euler tour starting with u. We traverse all adjacent vertices of u, if there is only one adjacent vertex, we immediately consider it. If there are more than one adjacent vertices, we consider an adjacent v only if edge u-v is not a bridge. How to find if a given is edge is bridge? We count number of vertices reachable from u. We remove edge u-v and again count number of reachable vertices from u. If number of reachable vertices are reduced, then edge u-v is a bridge. To count reachable vertices, we can either use BFS or DFS, we have used DFS in the above code. The function DFSCount(u) returns number of vertices reachable from u.
Once an edge is processed (included in Euler tour), we remove it from the graph. To remove the edge, we replace the vertex entry with -1 in adjacency list. Note that simply deleting the node may not work as the code is recursive and a parent call may be in middle of adjacency list.
PYTHON PROGRAMMING:
[pastacode lang=”python” manual=”%23%20Python%20program%20print%20Eulerian%20Trail%20in%20a%20given%20Eulerian%20or%20Semi-Eulerian%20Graph%0A%20%20%0Afrom%20collections%20import%20defaultdict%0A%20%20%0A%23This%20class%20represents%20an%20undirected%20graph%20using%20adjacency%20list%20representation%0Aclass%20Graph%3A%0A%20%20%0A%20%20%20%20def%20__init__(self%2Cvertices)%3A%0A%20%20%20%20%20%20%20%20self.V%3D%20vertices%20%23No.%20of%20vertices%0A%20%20%20%20%20%20%20%20self.graph%20%3D%20defaultdict(list)%20%23%20default%20dictionary%20to%20store%20graph%0A%20%20%20%20%20%20%20%20self.Time%20%3D%200%0A%20%20%0A%20%20%20%20%23%20function%20to%20add%20an%20edge%20to%20graph%0A%20%20%20%20def%20addEdge(self%2Cu%2Cv)%3A%0A%20%20%20%20%20%20%20%20self.graph%5Bu%5D.append(v)%0A%20%20%20%20%20%20%20%20self.graph%5Bv%5D.append(u)%0A%20%0A%20%20%20%20%23%20This%20function%20removes%20edge%20u-v%20from%20graph%20%0A%20%20%20%20def%20rmvEdge(self%2C%20u%2C%20v)%3A%0A%20%20%20%20%20%20%20%20for%20index%2C%20key%20in%20enumerate(self.graph%5Bu%5D)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20key%20%3D%3D%20v%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.graph%5Bu%5D.pop(index)%0A%20%20%20%20%20%20%20%20for%20index%2C%20key%20in%20enumerate(self.graph%5Bv%5D)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20key%20%3D%3D%20u%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.graph%5Bv%5D.pop(index)%0A%20%0A%20%20%20%20%23%20A%20DFS%20based%20function%20to%20count%20reachable%20vertices%20from%20v%0A%20%20%20%20def%20DFSCount(self%2C%20v%2C%20visited)%3A%0A%20%20%20%20%20%20%20%20count%20%3D%201%0A%20%20%20%20%20%20%20%20visited%5Bv%5D%20%3D%20True%0A%20%20%20%20%20%20%20%20for%20i%20in%20self.graph%5Bv%5D%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20visited%5Bi%5D%20%3D%3D%20False%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20count%20%3D%20count%20%2B%20self.DFSCount(i%2C%20visited)%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20return%20count%0A%20%0A%20%20%20%20%23%20The%20function%20to%20check%20if%20edge%20u-v%20can%20be%20considered%20as%20next%20edge%20in%0A%20%20%20%20%23%20Euler%20Tour%0A%20%20%20%20def%20isValidNextEdge(self%2C%20u%2C%20v)%3A%0A%20%20%20%20%20%20%20%20%23%20The%20edge%20u-v%20is%20valid%20in%20one%20of%20the%20following%20two%20cases%3A%0A%20%20%0A%20%20%20%20%20%20%20%20%23%20%201)%20If%20v%20is%20the%20only%20adjacent%20vertex%20of%20u%0A%20%20%20%20%20%20%20%20if%20len(self.graph%5Bu%5D)%20%3D%3D%201%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20True%0A%20%20%20%20%20%20%20%20else%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20”’%0A%20%20%20%20%20%20%20%20%20%20%20%20%202)%20If%20there%20are%20multiple%20adjacents%2C%20then%20u-v%20is%20not%20a%20bridge%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20Do%20following%20steps%20to%20check%20if%20u-v%20is%20a%20bridge%0A%20%20%0A%20%20%20%20%20%20%20%20%20%20%20%202.a)%20count%20of%20vertices%20reachable%20from%20u”’%20%0A%20%20%20%20%20%20%20%20%20%20%20%20visited%20%3D%5BFalse%5D*(self.V)%0A%20%20%20%20%20%20%20%20%20%20%20%20count1%20%3D%20self.DFSCount(u%2C%20visited)%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20”’2.b)%20Remove%20edge%20(u%2C%20v)%20and%20after%20removing%20the%20edge%2C%20count%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20vertices%20reachable%20from%20u”’%0A%20%20%20%20%20%20%20%20%20%20%20%20self.rmvEdge(u%2C%20v)%0A%20%20%20%20%20%20%20%20%20%20%20%20visited%20%3D%5BFalse%5D*(self.V)%0A%20%20%20%20%20%20%20%20%20%20%20%20count2%20%3D%20self.DFSCount(u%2C%20visited)%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%232.c)%20Add%20the%20edge%20back%20to%20the%20graph%0A%20%20%20%20%20%20%20%20%20%20%20%20self.addEdge(u%2Cv)%0A%20%0A%20%20%20%20%20%20%20%20%20%20%20%20%23%202.d)%20If%20count1%20is%20greater%2C%20then%20edge%20(u%2C%20v)%20is%20a%20bridge%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20False%20if%20count1%20%3E%20count2%20else%20True%0A%20%0A%20%0A%20%20%20%20%23%20Print%20Euler%20tour%20starting%20from%20vertex%20u%0A%20%20%20%20def%20printEulerUtil(self%2C%20u)%3A%0A%20%20%20%20%20%20%20%20%23Recur%20for%20all%20the%20vertices%20adjacent%20to%20this%20vertex%0A%20%20%20%20%20%20%20%20for%20v%20in%20self.graph%5Bu%5D%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%23If%20edge%20u-v%20is%20not%20removed%20and%20it’s%20a%20a%20valid%20next%20edge%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20self.isValidNextEdge(u%2C%20v)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20print(%22%25d-%25d%20%22%20%25(u%2Cv))%2C%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.rmvEdge(u%2C%20v)%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20self.printEulerUtil(v)%0A%20%0A%20%0A%20%20%20%20%20%0A%20%20%20%20”’The%20main%20function%20that%20print%20Eulerian%20Trail.%20It%20first%20finds%20an%20odd%0A%20%20%20degree%20vertex%20(if%20there%20is%20any)%20and%20then%20calls%20printEulerUtil()%0A%20%20%20to%20print%20the%20path%20”’%0A%20%20%20%20def%20printEulerTour(self)%3A%0A%20%20%20%20%20%20%20%20%23Find%20a%20vertex%20with%20odd%20degree%0A%20%20%20%20%20%20%20%20u%20%3D%200%0A%20%20%20%20%20%20%20%20for%20i%20in%20range(self.V)%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20if%20len(self.graph%5Bi%5D)%20%252%20!%3D%200%20%3A%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20u%20%3D%20i%0A%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20%20break%0A%20%20%20%20%20%20%20%20%23%20Print%20tour%20starting%20from%20odd%20vertex%0A%20%20%20%20%20%20%20%20print%20(%22%5Cn%22)%0A%20%20%20%20%20%20%20%20self.printEulerUtil(u)%0A%20%0A%23%20Create%20a%20graph%20given%20in%20the%20above%20diagram%0A%20%0Ag1%20%3D%20Graph(4)%0Ag1.addEdge(0%2C%201)%0Ag1.addEdge(0%2C%202)%0Ag1.addEdge(1%2C%202)%0Ag1.addEdge(2%2C%203)%0Ag1.printEulerTour()%0A%20%0A%20%0Ag2%20%3D%20Graph(3)%0Ag2.addEdge(0%2C%201)%0Ag2.addEdge(1%2C%202)%0Ag2.addEdge(2%2C%200)%0Ag2.printEulerTour()%0A%20%0Ag3%20%3D%20Graph%20(5)%0Ag3.addEdge(1%2C%200)%0Ag3.addEdge(0%2C%202)%0Ag3.addEdge(2%2C%201)%0Ag3.addEdge(0%2C%203)%0Ag3.addEdge(3%2C%204)%0Ag3.addEdge(3%2C%202)%0Ag3.addEdge(3%2C%201)%0Ag3.addEdge(2%2C%204)%0Ag3.printEulerTour()%0A%20″ message=”” highlight=”” provider=”manual”/]Output:
2-0 0-1 1-2 2-3 0-1 1-2 2-0 0-1 1-2 2-0 0-3 3-4 4-2 2-3 3-1