Given a directed Eulerian graph, print an Euler circuit. Euler circuit is a path that traverses every edge of a graph, and the path ends on the starting vertex.

Examples:

Input : Adjacency list for the below graph Output : 0 -> 1 -> 2 -> 0 Input : Adjacency list for the below graph Output : 0 -> 6 -> 4 -> 5 -> 0 -> 1 -> 2 -> 3 -> 4 -> 2 -> 0 Explanation: In both the cases, we can trace the Euler circuit by following the edges as indicated in the output.

We have 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. The same problem can be solved using Fleury’s Algorithm, however its complexity is O(E*E). Using Heirholzer’s Algorithm, we can find the circuit/path in O(E), i.e., linear time.

Below is the Algorithm: ref ( wiki ). Remember that a directed graph has an Eulerian cycle if following conditions are true (1) All vertices with nonzero degree belong to a single strongly connected component. (2) In degree and out degree of every vertex is same. The algorithm assumes that the given graph has Eulerian Circuit.

- Choose any starting vertex v, and follow a trail of edges from that vertex until returning to v. It is not possible to get stuck at any vertex other than v, because indegree and outdegree of every vertex must be same, when the trail enters another vertex w there must be an unused edge leaving w.

The tour formed in this way is a closed tour, but may not cover all the vertices and edges of the initial graph. - As long as there exists a vertex u that belongs to the current tour but that has adjacent edges not part of the tour, start another trail from u, following unused edges until returning to u, and join the tour formed in this way to the previous tour.

Thus the idea is to keep following unused edges and removing them until we get stuck. Once we get stuck, we back-track to the nearest vertex in our current path that has unused edges, and we repeat the process until all the edges have been used. We can use another container to maintain the final path.

Let’s take an example:

Let the initial directed graph be as below Let's start our path from 0. Thus, curr_path = {0} and circuit = {} Now let's use the edge 0->1 Now, curr_path = {0,1} and circuit = {} similarly we reach up to 2 and then to 0 again as Now, curr_path = {0,1,2} and circuit = {} Then we go to 0, now since 0 haven't got any unused edge we put 0 in circuit and back track till we find an edge We then have curr_path = {0,1,2} and circuit = {0} Similarly when we backtrack to 2, we don't find any unused edge. Hence put 2 in circuit and backtrack again. curr_path = {0,1} and circuit = {0,2} After reaching 1 we go to through unused edge 1->3 and then 3->4, 4->1 until all edges have been traversed. The contents of the two containers look as: curr_path = {0,1,3,4,1} and circuit = {0,2} now as all edges have been used, the curr_path is popped one by one into circuit. Finally we've circuit = {0,2,1,4,3,1,0} We print the circuit in reverse to obtain the path followed. i.e.,0->1->3->4->1->1->2->0

Below is the C++ program for the same.

`// A C++ program to print Eulerian circuit in given ` `// directed graph using Hierholzer algorithm ` `#include <bits/stdc++.h> ` `using` `namespace` `std; ` ` ` `void` `printCircuit(vector< vector<` `int` `> > adj) ` `{ ` ` ` `// adj represents the adjacency list of ` ` ` `// the directed graph ` ` ` `// edge_count represents the number of edges ` ` ` `// emerging from a vertex ` ` ` `unordered_map<` `int` `,` `int` `> edge_count; ` ` ` ` ` `for` `(` `int` `i=0; i<adj.size(); i++) ` ` ` `{ ` ` ` `//find the count of edges to keep track ` ` ` `//of unused edges ` ` ` `edge_count[i] = adj[i].size(); ` ` ` `} ` ` ` ` ` `if` `(!adj.size()) ` ` ` `return` `; ` `//empty graph ` ` ` ` ` `// Maintain a stack to keep vertices ` ` ` `stack<` `int` `> curr_path; ` ` ` ` ` `// vector to store final circuit ` ` ` `vector<` `int` `> circuit; ` ` ` ` ` `// start from any vertex ` ` ` `curr_path.push(0); ` ` ` `int` `curr_v = 0; ` `// Current vertex ` ` ` ` ` `while` `(!curr_path.empty()) ` ` ` `{ ` ` ` `// If there's remaining edge ` ` ` `if` `(edge_count[curr_v]) ` ` ` `{ ` ` ` `// Push the vertex ` ` ` `curr_path.push(curr_v); ` ` ` ` ` `// Find the next vertex using an edge ` ` ` `int` `next_v = adj[curr_v].back(); ` ` ` ` ` `// and remove that edge ` ` ` `edge_count[curr_v]--; ` ` ` `adj[curr_v].pop_back(); ` ` ` ` ` `// Move to next vertex ` ` ` `curr_v = next_v; ` ` ` `} ` ` ` ` ` `// back-track to find remaining circuit ` ` ` `else` ` ` `{ ` ` ` `circuit.push_back(curr_v); ` ` ` ` ` `// Back-tracking ` ` ` `curr_v = curr_path.top(); ` ` ` `curr_path.pop(); ` ` ` `} ` ` ` `} ` ` ` ` ` `// we've got the circuit, now print it in reverse ` ` ` `for` `(` `int` `i=circuit.size()-1; i>=0; i--) ` ` ` `{ ` ` ` `cout << circuit[i]; ` ` ` `if` `(i) ` ` ` `cout<<` `" -> "` `; ` ` ` `} ` `} ` ` ` `// Driver program to check the above function ` `int` `main() ` `{ ` ` ` `vector< vector<` `int` `> > adj1, adj2; ` ` ` ` ` `// Input Graph 1 ` ` ` `adj1.resize(3); ` ` ` ` ` `// Build the edges ` ` ` `adj1[0].push_back(1); ` ` ` `adj1[1].push_back(2); ` ` ` `adj1[2].push_back(0); ` ` ` `printCircuit(adj1); ` ` ` `cout << endl; ` ` ` ` ` `// Input Graph 2 ` ` ` `adj2.resize(7); ` ` ` `adj2[0].push_back(1); ` ` ` `adj2[0].push_back(6); ` ` ` `adj2[1].push_back(2); ` ` ` `adj2[2].push_back(0); ` ` ` `adj2[2].push_back(3); ` ` ` `adj2[3].push_back(4); ` ` ` `adj2[4].push_back(2); ` ` ` `adj2[4].push_back(5); ` ` ` `adj2[5].push_back(0); ` ` ` `adj2[6].push_back(4); ` ` ` `printCircuit(adj2); ` ` ` ` ` `return` `0; ` `} ` |

Output:

0 -> 1 -> 2 -> 0 0 -> 6 -> 4 -> 5 -> 0 -> 1 -> 2 -> 3 -> 4 -> 2 -> 0

**Time Complexity :** O(V+E).

Please write comments if you find anything incorrect, or you want to share more information about the topic discussed above.

## leave a comment

## 0 Comments