Class DirectedDFS

  • public class DirectedDFS
    extends Object
    The DirectedDFS class represents a data type for determining the vertices reachable from a given source vertex s (or set of source vertices) in a digraph. For versions that find the paths, see DepthFirstDirectedPaths and BreadthFirstDirectedPaths.

    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. Each instance method takes Θ(1) time. It uses Θ(V) extra space (not including the digraph).

    For additional documentation, see Section 4.2 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

    Robert Sedgewick, Kevin Wayne
    • Constructor Detail

      • DirectedDFS

        public DirectedDFS​(Digraph G,
                           int s)
        Computes the vertices in digraph G that are reachable from the source vertex s.
        G - the digraph
        s - the source vertex
        IllegalArgumentException - unless 0 <= s < V
    • Method Detail

      • marked

        public boolean marked​(int v)
        Is there a directed path from the source vertex (or any of the source vertices) and vertex v?
        v - the vertex
        true if there is a directed path, false otherwise
        IllegalArgumentException - unless 0 <= v < V
      • count

        public int count()
        Returns the number of vertices reachable from the source vertex (or source vertices).
        the number of vertices reachable from the source vertex (or source vertices)
      • main

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