Class Cycle

java.lang.Object

Cycle

public class Cycle
extends java.lang.Object

The Cycle class represents a data type for determining whether an undirected graph has a cycle. The hasCycle operation determines whether the graph has a cycle and, if so, the cycle operation returns one.

This implementation uses depth-first search. The constructor takes time proportional to V + E (in the worst case), where V is the number of vertices and E is the number of edges. Afterwards, the hasCycle operation takes constant time; the cycle operation takes time proportional to the length of the cycle.

For additional documentation, see Section 4.1 of Algorithms, 4th Edition, by Robert Sedgewick and Kevin Wayne.

Constructor Summary

Constructors

Constructor and Description
Cycle(Graph G) Determines whether the undirected graph G has a cycle and, if so, finds such a cycle.

Method Summary

Methods

Modifier and Type	Method and Description
java.lang.Iterable<java.lang.Integer>	cycle() Returns a cycle if the graph has a cycle, and null otherwise.
boolean	hasCycle() Does the graph have a cycle?
static void	main(java.lang.String[] args) Unit tests the Cycle data type.

Methods inherited from class java.lang.Object

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

Constructor Detail

Cycle

public Cycle(Graph G)

Determines whether the undirected graph G has a cycle and, if so, finds such a cycle.

Parameters:

G - the graph

Method Detail

hasCycle

public boolean hasCycle()

Does the graph have a cycle?

Returns:

true if the graph has a cycle, false otherwise

cycle

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

Returns a cycle if the graph has a cycle, and null otherwise.

Returns:

a cycle (as an iterable) if the graph has a cycle, and null otherwise

main

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

Unit tests the Cycle data type.