public class DirectedCycleX extends Object
DirectedCycleX
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, queue-based 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. Afterwards, the hasCycle operation takes constant time; the cycle operation takes time proportional to the length of the cycle.
See DirectedCycle
for a recursive version that uses depth-first search.
See Topological
or TopologicalX
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.
Constructor and Description |
---|
DirectedCycleX(Digraph G) |
public DirectedCycleX(Digraph G)
public Iterable<Integer> cycle()
null
otherwise.null
otherwisepublic boolean hasCycle()
true
if the digraph has a directed cycle, false
otherwisepublic static void main(String[] args)