Euler path for directed graph?

Solution 1:

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.