Package algs41
Class EulerianPath
java.lang.Object
algs41.EulerianPath
The
EulerianPath
class represents a data type
for finding an Eulerian path in a graph.
An Eulerian path is a path (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 cycles in graphs, see EulerianCycle
.
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
-
Nested Class Summary
-
Field Summary
-
Constructor Summary
ConstructorDescriptionComputes an Eulerian path in the specified graph, if one exists. -
Method Summary
Modifier and TypeMethodDescriptionprivate boolean
boolean
Returns true if the graph has an Eulerian path.static void
Unit tests theEulerianPath
data type.private static int
path()
Returns the sequence of vertices on an Eulerian path.private static boolean
The code below is solely for testing correctness of the data type.private static void
-
Field Details
-
path
-
-
Constructor Details
-
EulerianPath
Computes an Eulerian path in the specified graph, if one exists.- Parameters:
G
- the graph
-
-
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 graph has an Eulerian path.- Returns:
true
if the graph has an Eulerian path;false
otherwise
-
nonIsolatedVertex
-
satisfiesNecessaryAndSufficientConditions
The code below is solely for testing correctness of the data type. -
certifySolution
-
unitTest
-
main
Unit tests theEulerianPath
data type.- Parameters:
args
- the command-line arguments
-