public class EulerianCycle extends Object
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 runs in O(E + V) time, and uses O(E + V) extra space, where E is the number of edges and V the number of vertices All other methods take O(1) time.
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.
Constructor and Description |
---|
EulerianCycle(Graph G)
Computes an Eulerian cycle in the specified graph, if one exists.
|
public EulerianCycle(Graph G)
G
- the graphpublic Iterable<Integer> cycle()
null
if no such cyclepublic boolean hasEulerianCycle()
true
if the graph has an Eulerian cycle;
false
otherwisepublic static void main(String[] args)
EulerianCycle
data type.args
- the command-line arguments