# Euler path for directed graph?

How do we find Euler path for directed graphs? I don't seem to get the algorithm below!

Algorithm

To find the Euclidean cycle in a digraph (enumerate the edges in the cycle), using a greedy process,

Preprocess the graph and make and in-tree with root $r$, compute $G¯$ (reverse all edges). Then perform Breadth first search to get the tree $T$. This is $O(|E|+|V|)$.

When we perform the algorithm, we'll get the list,

$r\to d\to a\to b\to c\to d\to c\to a\to r$

You can try out following algorithm for finding out Euler Path in Directed graph:

Let number of edges in initial graph be $$E$$, and number of vertices in initial graph be $$V$$.

### Step 1

Check the following conditions to determine if Euler Path can exist or not (time complexity $$O(V)$$):

1. There should be a single vertex in graph which has $$\text{indegree}+1=\text{outdegree}$$, lets call this vertex an.
2. There should be a single vertex in graph which has $$\text{indegree}=\text{outdegree}+1$$, lets call this vertex bn.
3. Rest all vertices should have $$\text{indegree}=\text{outdegree}$$.

If either of the above condition fails Euler Path can't exist.

### Step 2

Add an edge from vertex bn to an in existing graph, now for all vertices $$\text{indegree}=\text{outdegree}$$ holds true (time complexity $$O(1)$$).

### Step 3

Try to find Euler cycle in this modified graph using Hierholzer’s algorithm (time complexity $$O(V+E)$$).

1. Choose any vertex $$v$$ and push it onto a stack. Initially all edges are unmarked.
2. While the stack is nonempty, look at the top vertex, $$u$$, on the stack. If $$u$$ has an unmarked incident edge, say, to a vertex $$w$$, then push $$w$$ onto the stack and mark the edge $$uw$$. On the other hand, if $$u$$ has no unmarked incident edge, then pop $$u$$ off the stack and print it.
3. When the stack is empty, you will have printed a sequence of vertices that correspond to an Eulerian circuit.

Look into this Blog for better explanation of Hierholzer’s algorithm.

### Step 4

Check if the printed cycle has sufficient number of edges included or not. If not then the original graph might be disconnected and Euler Path can't exist in this case.

### Step 5

In the cycle so determined in Step 3, remove the edge from bn to an, now start traversing this modified cycle (not a cycle anymore, it's a Path) from bn. Finally you'll end up on an, so this path is Euler Path of original graph.

• "a) There should be a single vertex in graph which has (indegree+1==outdegree), lets call this vertex 'an'." That is not correct. There should be NO MORE than a single vertex with indegree+1==outdegree. Same applies to b) Circle graph is also a path. Commented Sep 6, 2019 at 16:16
• @DraifKroneg I agree with you, there should be exactly (not greater or less) one node satisfying the conditions I mentioned.
– JVJ
Commented Mar 24, 2020 at 14:19
• Here is the simple implementation of this algorithm - gist.github.com/mejanvijay/5995a9cf0665763714e09553afc37d74
– JVJ
Commented Mar 24, 2020 at 16:35