Package algs42
Class DirectedEulerianCycle
java.lang.Object
algs42.DirectedEulerianCycle
The
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.
- Author:
- Robert Sedgewick, Kevin Wayne, Nate Liu
-
Field Summary
-
Constructor Summary
ConstructorDescriptionComputes an Eulerian cycle in the specified digraph, if one exists. -
Method Summary
Modifier and TypeMethodDescriptionprivate boolean
cycle()
Returns the sequence of vertices on an Eulerian cycle.boolean
Returns true if the digraph has an Eulerian cycle.static void
Unit tests theDirectedEulerianCycle
data type.private static int
private static boolean
The code below is solely for testing correctness of the data type.private static void
-
Field Details
-
cycle
-
-
Constructor Details
-
DirectedEulerianCycle
Computes an Eulerian cycle in the specified digraph, if one exists.- Parameters:
G
- the digraph
-
-
Method Details
-
cycle
Returns the sequence of vertices on an Eulerian cycle.- Returns:
- the sequence of vertices on an Eulerian cycle;
null
if no such cycle
-
hasEulerianCycle
Returns true if the digraph has an Eulerian cycle.- Returns:
true
if the digraph has an Eulerian cycle;false
otherwise
-
nonIsolatedVertex
-
satisfiesNecessaryAndSufficientConditions
The code below is solely for testing correctness of the data type. -
certifySolution
-
unitTest
-
main
Unit tests theDirectedEulerianCycle
data type.- Parameters:
args
- the command-line arguments
-