Class NonrecursiveDFS

  • public class NonrecursiveDFS
    extends Object
    The NonrecursiveDFS class represents a data type for finding the vertices connected to a source vertex s in the undirected graph.

    This implementation uses a nonrecursive version of depth-first search with an explicit stack. See DepthFirstSearch for the classic 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. The marked(int) 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

      • NonrecursiveDFS

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

      • marked

        public boolean marked​(int v)
        Is vertex v connected to the source vertex s?
        v - the vertex
        true if vertex v is connected to the source vertex s, and false otherwise
        IllegalArgumentException - unless 0 <= v < V
      • main

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