Check whether a directed graph is Eulerian

Given a directed graph, check whether it has an Eulerian path or not. An Eulerian path (or Eulerian trail) is a path in a graph that visits every edge exactly once.

The following graph has an Eulerian path since it is possible to construct a path that visits each edge exactly once. The Eulerian path is 0 —> 1 —> 2 —> 3 —> 0 —> 5 —> 4 —> 3 —> 1 —> 4 .

Related Post:

A directed graph has an Eulerian path if and only if the following conditions are satisfied:

1. At most one vertex in the graph has out-degree = 1 + in-degree , and at most one vertex in the graph has in-degree = 1 + out-degree . All the remaining vertices have in-degree == out-degree .
2. All vertices with a non-zero degree belong to a single connected component of the underlying undirected graph. In other words, if one removes the “directness” of edges, then the graph without isolated vertices should be connected.

For example, in the above graph, the only vertex 0 has out-degree one more than the in-degree, and vertex 4 has in-degree one more than the out-degree. Every other vertex has equal in-degree and out-degree, and the non-isolated vertices are weakly connected. The algorithm can be implemented as follows in C++, Java, and Python: