edu.princeton.cs.algs4

Class EulerianPath

java.lang.Object

edu.princeton.cs.algs4.EulerianPath

public class EulerianPath
extends java.lang.Object

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.

Constructor Summary

Constructors

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

Method Summary

Modifier and Type	Method and Description
boolean	hasEulerianPath() Returns true if the graph has an Eulerian path.
static void	main(java.lang.String[] args) Unit tests the EulerianPath data type.
java.lang.Iterable<java.lang.Integer>	path() Returns the sequence of vertices on an Eulerian path.

Methods inherited from class java.lang.Object

equals, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

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 java.lang.Iterable<java.lang.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(java.lang.String[] args)

Unit tests the EulerianPath data type.

Parameters:

args - the command-line arguments