Package edu.princeton.cs.algs4
Class DirectedCycleX
 Object

 edu.princeton.cs.algs4.DirectedCycleX

public class DirectedCycleX extends Object
TheDirectedCycleX
class represents a data type for determining whether a digraph has a directed cycle. The hasCycle operation determines whether the digraph has a simple directed cycle and, if so, the cycle operation returns one.This implementation uses a nonrecursive, queuebased algorithm. 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. Each instance method takes Θ(1) time. It uses Θ(V) extra space (not including the digraph).
See
DirectedCycle
for a recursive version that uses depthfirst search. SeeTopological
orTopologicalX
to compute a topological order when the digraph is acyclic.For additional documentation, see Section 4.2 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
 Author:
 Robert Sedgewick, Kevin Wayne


Constructor Summary
Constructors Constructor Description DirectedCycleX(Digraph G)

Method Summary
All Methods Static Methods Instance Methods Concrete Methods Modifier and Type Method Description Iterable<Integer>
cycle()
Returns a directed cycle if the digraph has a directed cycle, andnull
otherwise.boolean
hasCycle()
Does the digraph have a directed cycle?static void
main(String[] args)



Constructor Detail

DirectedCycleX
public DirectedCycleX(Digraph G)


Method Detail

cycle
public Iterable<Integer> cycle()
Returns a directed cycle if the digraph has a directed cycle, andnull
otherwise. Returns:
 a directed cycle (as an iterable) if the digraph has a directed cycle,
and
null
otherwise

hasCycle
public boolean hasCycle()
Does the digraph have a directed cycle? Returns:
true
if the digraph has a directed cycle,false
otherwise

main
public static void main(String[] args)

