Class DirectedCycleX

  • public class DirectedCycleX
    extends Object
    The 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. Each instance method takes Θ(1) time. It uses Θ(V) extra space (not including the digraph).

    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.

    Robert Sedgewick, Kevin Wayne
    • 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, and null otherwise.
        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?
        true if the digraph has a directed cycle, false otherwise
      • main

        public static void main​(String[] args)