Nikhil Kumar SinghVrishchik

An Eulerian path is a path of edges that visit all edges in a graph exactly once.

We can find an Eulerian path on the graph below only if we start at specific nodes.

But, if we change the starting point we might not get the desired result, like in the below example:

An Eulerian circuit is an Eulerian path that starts and ends at the same vertex.

In the above example, we can see that our graph does have an Eulerian circuit. If your graph does not contain an Eulerian cycle then you may not be able to return to the start node or you will not be able to visit all edges of the graph.

To support our above statement let’s take another example. This is basically the same but with some modification. We start from the same point.

The conditions required for a valid Eulerian path/circuit:

**Eulerian circuit -** every vertex has an even degree.

**Eulerian path -** either every vertex has an even degree or exactly two vertices have an odd degree.

**Eulerian circuit -** every vertex has equal indegree and outdegree.

**Eulerian path -** at most one vertex has (outdegree) - (indegree) = 1 and at most one vertex has (indegree) - (outdegree) = 1, and all other vertices have equal in and outdegrees.

Step one to finding an Eulerian path is determining if an Eulerian path even exists.

Recall that for an Eulerian path to exist, at most one vertex has (outdegree) - (indegree) = 1 and at most one vertex has (indegree) - (outdegree) = 1, and all other vertices have equal in and outdegrees.

In our above example we have calculated both in and outdegree of each node, and now we can confirm our conditions for a Eulerian path. No nodes have out[i] - in[i] > 1 or in[i] - out[i] > 1 and there are just the right amount of start/end nodes.

Node one is the only node with exactly one extra outgoing edge, so it’s our only valid start node. Similarly, node six is the only node with exactly one extra incoming edge, so it will end up being the end node.

When we randomly select edges during the depth-first search (DFS), we might reach the end node without traversing all the edges in our graph.

Every time an edge is taken we reduce the outgoing edge count in the out array.

When the DFS is stuck, meaning there are no more outgoing edges, then we backtrack and add the current node to the solution.

While backtracking, if the current node has any remaining unvisited edges (white edges), we follow any of them, calling our DFS method recursively to extend the Eulerian path. We can verify there still are outgoing edges by checking if out[i] != 0.

For the approach of our above example we would get:

**[1,3,5,6,3,2,4,3,1,2,2,4,6]****as the result**

The time complexity of the algorithm is **O(E).** All the other operations are linear (calculating in/out-degree).

**Code:**

```
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
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
```

```
#include<bits/stdc++.h>
using namespace std;
map < int, vector < int >> graph;
vector < int > path;
vector < int > in , out;
int edges;
int n;
void setUp() {
in .resize(n);
out.resize(n);
edges = 0;
for (int from = 1; from < n; from++)
for (auto to: graph[from]) {
in [to]++, out[from]++;
edges++;
}
}
bool hasEulerianPath() {
if (edges == 0) return false;
int startNodes = 0, endNodes = 0;
for (int i = 0; i < n; i++) {
if (out[i] - in [i] > 1 || in [i] - out[i] > 1) return false;
else if (out[i] - in [i] == 1) startNodes++;
else if ( in [i] - out[i] == 1) endNodes++;
}
return (endNodes == 0 && startNodes == 0) || (endNodes == 1 && startNodes == 1);
}
int findStartNode() {
int start = 0;
for (int i = 0; i < n; i++) {
if (out[i] - in [i] == 1) return i;
if (out[i] > 0) start = i;
}
return start;
}
void dfs(int at) {
while (out[at]) {
int next = graph[at][--out[at]];
dfs(next);
}
path.push_back(at);
}
vector < int > getEulerianPath() {
setUp();
if (!hasEulerianPath()) return {};
dfs(findStartNode());
if (path.size() != edges + 1) return {};
reverse(path.begin(), path.end());
return path;
}
void addEdge(int from, int to) {
graph[from].push_back(to);
}
int main() {
n = 7;
addEdge(1, 2);
addEdge(1, 3);
addEdge(2, 2);
addEdge(2, 4);
addEdge(2, 4);
addEdge(3, 1);
addEdge(3, 2);
addEdge(3, 5);
addEdge(4, 3);
addEdge(4, 6);
addEdge(5, 6);
addEdge(6, 3);
vector < int > path = getEulerianPath();
for (auto x: path) cout << x << " ";
}
```

Running the code gives the exact output as we computed above **[1,3,5,6,3,2,4,3,1,2,2,4,6]**.

Discuss this article in the forums
Basic methods for searching graphs
Introduction
Stack
Depth First Search
...

Read More Setting up the Applet
Installing Java Runtime Environment
* Download the latest version of JRE (Java Runtime ...

Read More Types of Data Structure
There are two types of data structures; linear and nonlinear. In linear data
structure...

Read More © 2021 TopcoderPolicies