Package algs41
Class EulerianCycle
java.lang.Object
algs41.EulerianCycle
The
EulerianCycle
class represents a data type
for finding an Eulerian cycle or path in a graph.
An Eulerian cycle is a cycle (not necessarily simple) that
uses every edge in the graph 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 Θ(E + V) extra space in the worst case (not including the graph).
To compute Eulerian paths in graphs, see EulerianPath
.
To compute Eulerian cycles and paths in digraphs, see
DirectedEulerianCycle
and DirectedEulerianPath
.
For additional documentation, see Section 4.1 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
- Author:
- Robert Sedgewick, Kevin Wayne, Nate Liu
-
Constructor Summary
ConstructorDescriptionComputes an Eulerian cycle in the specified graph, if one exists. -
Method Summary
-
Constructor Details
-
EulerianCycle
Computes an Eulerian cycle in the specified graph, if one exists.- Parameters:
G
- the graph
-
-
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 graph has an Eulerian cycle.- Returns:
true
if the graph has an Eulerian cycle;false
otherwise
-
main
Unit tests theEulerianCycle
data type.- Parameters:
args
- the command-line arguments
-