Eulerian Path and Circuit in Graphs

Eulerian Path

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:

Eulerian Circuit

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:

Undirected Graph:

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.

Directed Graph:

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.

Finding an Eulerian Path (Directed Graph)

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.

DFS Backtrack Approach:

• 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

Time Complexity:

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].