public class DirectedEulerianCycle extends Object
DirectedEulerianCycleclass represents a data type for finding an Eulerian cycle or path in a digraph. An Eulerian cycle is a cycle (not necessarily simple) that uses every edge in the digraph exactly once.
This implementation uses a nonrecursive depth-first search. The constructor takes Θ(E + V) time in the worst case, where E is the number of edges and V is the number of vertices Each instance method takes Θ(1) time. It uses Θ(V) extra space (not including the digraph).
To compute Eulerian paths in digraphs, see
To compute Eulerian cycles and paths in undirected graphs, see
For additional documentation, see Section 4.2 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
|Constructor and Description|
Computes an Eulerian cycle in the specified digraph, if one exists.
|Modifier and Type||Method and Description|
Returns the sequence of vertices on an Eulerian cycle.
Returns true if the digraph has an Eulerian cycle.
Unit tests the
public DirectedEulerianCycle(Digraph G)
G- the digraph
public Iterable<Integer> cycle()
nullif no such cycle
public boolean hasEulerianCycle()
trueif the digraph has an Eulerian cycle;
public static void main(String args)
args- the command-line arguments