2
$\begingroup$

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|)$. enter image description here

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$

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "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. $\endgroup$ – Draif Kroneg Sep 6 at 16:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.