# 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 ( Time Complexity : O( V ) ) to determine if Euler Path can exist or not :

     a) There should be a single vertex in graph which has (indegree+1==outdegree), lets call this vertex 'an'.
b) There should be a single vertex in graph which has (indegree==outdegree+1), lets call this vertex 'bn'.
c) Rest all vertices should have (indegree==outdegree)
If either of the above condition fails Euler Path can't exist.


Step 2 :

Add a edge from vertex 'bn' to 'an' in existing graph, now for all vertices (indegree==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 ) )

     a) Choose any vertex v and push it onto a stack. Initially all edges are unmarked.
b) 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.
c) 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 cycle so printed is sufficient number of edges included or not. If not then 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 a edge from 'bn' to 'an', now start traversing this modified cycle (Not a cycle any more, 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. – Draif Kroneg Sep 6 at 16:16