Package algs42
Class DirectedEulerianPath
java.lang.Object
algs42.DirectedEulerianPath
The
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 take Θ(E + V) time in the worst case, where E is the number of edges and V is the number of vertices. It uses Θ(V) extra space (not including the digraph).
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.
- Author:
- Robert Sedgewick, Kevin Wayne, Nate Liu
-
Constructor Summary
ConstructorDescriptionComputes an Eulerian path in the specified digraph, if one exists. -
Method Summary
-
Constructor Details
-
DirectedEulerianPath
Computes an Eulerian path in the specified digraph, if one exists.- Parameters:
G
- the digraph
-
-
Method Details
-
path
Returns the sequence of vertices on an Eulerian path.- Returns:
- the sequence of vertices on an Eulerian path;
null
if no such path
-
hasEulerianPath
Returns true if the digraph has an Eulerian path.- Returns:
true
if the digraph has an Eulerian path;false
otherwise
-
main
Unit tests theDirectedEulerianPath
data type.- Parameters:
args
- the command-line arguments
-