public class DirectedEulerianCycle extends Object
DirectedEulerianCycle
class 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 DirectedEulerianPath
.
To compute Eulerian cycles and paths in undirected graphs, see
EulerianCycle
and EulerianPath
.
For additional documentation, see Section 4.2 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
Constructor and Description |
---|
DirectedEulerianCycle(Digraph G)
Computes an Eulerian cycle in the specified digraph, if one exists.
|
Modifier and Type | Method and Description |
---|---|
Iterable<Integer> |
cycle()
Returns the sequence of vertices on an Eulerian cycle.
|
boolean |
hasEulerianCycle()
Returns true if the digraph has an Eulerian cycle.
|
static void |
main(String[] args)
Unit tests the
DirectedEulerianCycle data type. |
public DirectedEulerianCycle(Digraph G)
G
- the digraphpublic Iterable<Integer> cycle()
null
if no such cyclepublic boolean hasEulerianCycle()
true
if the digraph has an Eulerian cycle;
false
otherwisepublic static void main(String[] args)
DirectedEulerianCycle
data type.args
- the command-line arguments