edu.princeton.cs.algs4

Class Cycle

java.lang.Object

edu.princeton.cs.algs4.Cycle

public class Cycle
extends java.lang.Object

The Cycle class represents a data type for determining whether an undirected graph has a simple 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

Modifier and Type	Method and Description
java.lang.Iterable<java.lang.Integer>	cycle() Returns a cycle in the graph G.
boolean	hasCycle() Returns true if the graph G has a cycle.
static void	main(java.lang.String[] args) Unit tests the Cycle data type.

Methods inherited from class java.lang.Object

equals, 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 undirected graph

Method Detail

hasCycle

public boolean hasCycle()

Returns true if the graph G has a cycle.

Returns:

true if the graph has a cycle; false otherwise

cycle

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

Returns a cycle in the graph G.

Returns:

a cycle if the graph G has a cycle, and null otherwise

main

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

Unit tests the Cycle data type.

Parameters:

args - the command-line arguments