Class DepthFirstDirectedPaths


  • public class DepthFirstDirectedPaths
    extends Object
    The DepthFirstDirectedPaths class represents a data type for finding directed paths from a source vertex s to every other vertex in the digraph.

    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 DepthFirstDirectedPaths for a nonrecursive implementation. For additional documentation, see Section 4.2 of Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.

    Author:
    Robert Sedgewick, Kevin Wayne
    • Constructor Detail

      • DepthFirstDirectedPaths

        public DepthFirstDirectedPaths​(Digraph G,
                                       int s)
        Computes a directed path from s to every other vertex in digraph G.
        Parameters:
        G - the digraph
        s - the source vertex
        Throws:
        IllegalArgumentException - unless 0 <= s < V
    • Method Detail

      • hasPathTo

        public boolean hasPathTo​(int v)
        Is there a directed path from the source vertex s to vertex v?
        Parameters:
        v - the vertex
        Returns:
        true if there is a directed path from the source vertex s to vertex v, false otherwise
        Throws:
        IllegalArgumentException - unless 0 <= v < V
      • pathTo

        public Iterable<Integer> pathTo​(int v)
        Returns a directed path from the source vertex s to vertex v, or null if no such path.
        Parameters:
        v - the vertex
        Returns:
        the sequence of vertices on a directed path from the source vertex s to vertex v, as an Iterable
        Throws:
        IllegalArgumentException - unless 0 <= v < V
      • main

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