public class DirectedEulerianPath extends Object
DirectedEulerianPath
class represents a data type
for finding an Eulerian path in a digraph.
An Eulerian path is a path (not necessarily simple) that
uses every edge in the digraph exactly once.
This implementation uses a nonrecursive depth-first search. The constructor runs in O(E + V) time, and uses O(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 cycles in digraphs, see DirectedEulerianCycle
.
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 |
---|
DirectedEulerianPath(Digraph G)
Computes an Eulerian path in the specified digraph, if one exists.
|
public DirectedEulerianPath(Digraph G)
G
- the digraphpublic Iterable<Integer> path()
null
if no such pathpublic boolean hasEulerianPath()
true
if the digraph has an Eulerian path;
false
otherwisepublic static void main(String[] args)
DirectedEulerianPath
data type.args
- the command-line arguments