Class DepthFirstSearch

  • public class DepthFirstSearch
    extends Object
    The DepthFirstSearch class represents a data type for determining the vertices connected to a given source vertex s in an undirected graph. For versions that find the paths, see DepthFirstPaths and BreadthFirstPaths.

    This implementation uses depth-first search. See NonrecursiveDFS for a non-recursive version. 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 graph).

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

    Robert Sedgewick, Kevin Wayne
    • Constructor Detail

      • DepthFirstSearch

        public DepthFirstSearch​(Graph G,
                                int s)
        Computes the vertices in graph G that are connected to the source vertex s.
        G - the graph
        s - the source vertex
        IllegalArgumentException - unless 0 <= s < V
    • Method Detail

      • marked

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

        public int count()
        Returns the number of vertices connected to the source vertex s.
        the number of vertices connected to the source vertex s
      • main

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