Package edu.princeton.cs.algs4
Class EulerianPath
 Object

 edu.princeton.cs.algs4.EulerianPath

public class EulerianPath extends Object
TheEulerianPath
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 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 Θ(E + V) extra space in the worst case (not including the digraph).
To compute Eulerian cycles in graphs, see
EulerianCycle
. To compute Eulerian cycles and paths in digraphs, seeDirectedEulerianCycle
andDirectedEulerianPath
.For additional documentation, see Section 4.1 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
 Author:
 Robert Sedgewick, Kevin Wayne, Nate Liu


Constructor Summary
Constructors Constructor Description EulerianPath(Graph G)
Computes an Eulerian path in the specified graph, if one exists.

Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description boolean
hasEulerianPath()
Returns true if the graph has an Eulerian path.static void
main(String[] args)
Unit tests theEulerianPath
data type.Iterable<Integer>
path()
Returns the sequence of vertices on an Eulerian path.



Constructor Detail

EulerianPath
public EulerianPath(Graph G)
Computes an Eulerian path in the specified graph, if one exists. Parameters:
G
 the graph


Method Detail

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

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

