edu.princeton.cs.algs4

Class EulerianCycle

java.lang.Object

edu.princeton.cs.algs4.EulerianCycle

public class EulerianCycle
extends java.lang.Object

The EulerianCycle class represents a data type for finding an Eulerian cycle or path in a graph. An Eulerian cycle is a cycle (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 paths in graphs, see EulerianPath. 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
EulerianCycle(Graph G) Computes an Eulerian cycle in the specified graph, if one exists.

Method Summary

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

Methods inherited from class java.lang.Object

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

Constructor Detail

EulerianCycle

public EulerianCycle(Graph G)

Computes an Eulerian cycle in the specified graph, if one exists.

Parameters:

G - the graph

Method Detail

cycle

public java.lang.Iterable<java.lang.Integer> cycle()

Returns the sequence of vertices on an Eulerian cycle.

Returns:

the sequence of vertices on an Eulerian cycle; null if no such cycle

hasEulerianCycle

public boolean hasEulerianCycle()

Returns true if the graph has an Eulerian cycle.

Returns:

true if the graph has an Eulerian cycle; false otherwise

main

public static void main(java.lang.String[] args)

Unit tests the EulerianCycle data type.

Parameters:

args - the command-line arguments