Class DirectedCycle

  • public class DirectedCycle
    extends Object
    The DirectedCycle 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 depth-first search. The constructor takes Θ(V + E) time 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 Topological to compute a topological order if 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

      • DirectedCycle

        public DirectedCycle​(Digraph G)
        Determines whether the digraph G has a directed cycle and, if so, finds such a cycle.
        G - the digraph
    • Method Detail

      • hasCycle

        public boolean hasCycle()
        Does the digraph have a directed cycle?
        true if the digraph has a directed cycle, false otherwise
      • 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
      • main

        public static void main​(String[] args)
        Unit tests the DirectedCycle data type.
        args - the command-line arguments