Package edu.princeton.cs.algs4
Class DirectedEulerianCycle
 Object

 edu.princeton.cs.algs4.DirectedEulerianCycle

public class DirectedEulerianCycle extends Object
TheDirectedEulerianCycle
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 depthfirst 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, seeEulerianCycle
andEulerianPath
.For additional documentation, see Section 4.2 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
 Author:
 Robert Sedgewick, Kevin Wayne, Nate Liu


Constructor Summary
Constructors Constructor Description DirectedEulerianCycle(Digraph G)
Computes an Eulerian cycle in the specified digraph, if one exists.

Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method 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 theDirectedEulerianCycle
data type.



Constructor Detail

DirectedEulerianCycle
public DirectedEulerianCycle(Digraph G)
Computes an Eulerian cycle in the specified digraph, if one exists. Parameters:
G
 the digraph


Method Detail

cycle
public Iterable<Integer> 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
public boolean hasEulerianCycle()
Returns true if the digraph has an Eulerian cycle. Returns:
true
if the digraph has an Eulerian cycle;false
otherwise

main
public static void main(String[] args)
Unit tests theDirectedEulerianCycle
data type. Parameters:
args
 the commandline arguments

