/****************************************************************************** * Compilation: javac NonrecursiveDirectedDFS.java * Execution: java NonrecursiveDirectedDFS digraph.txt s * Dependencies: Digraph.java Queue.java Stack.java StdOut.java * Data files: https://algs4.cs.princeton.edu/42digraph/tinyDG.txt * https://algs4.cs.princeton.edu/42digraph/mediumDG.txt * https://algs4.cs.princeton.edu/42digraph/largeDG.txt * * Run nonrecurisve depth-first search on a directed graph. * Runs in O(E + V) time. * * Explores the vertices in exactly the same order as DirectedDFS.java. * * * % java NonrecursiveDirectedDFS tinyDG.txt 1 * 1 * * % java NonrecursiveDirectedDFS tinyDG.txt 2 * 0 1 2 3 4 5 * ******************************************************************************/ import java.util.Iterator; /** * The {@code NonrecursiveDirectedDFS} class represents a data type for finding * the vertices reachable from a source vertex s in the digraph. *
* This implementation uses a nonrecursive version of depth-first search * with an explicit stack. * 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). *
* For additional documentation,
* see Section 4.2 of
* Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne.
*
* @author Robert Sedgewick
* @author Kevin Wayne
*/
public class NonrecursiveDirectedDFS {
private boolean[] marked; // marked[v] = is there an s->v path?
/**
* Computes the vertices reachable from the source vertex {@code s} in the digraph {@code G}.
* @param G the digraph
* @param s the source vertex
* @throws IllegalArgumentException unless {@code 0 <= s < V}
*/
public NonrecursiveDirectedDFS(Digraph G, int s) {
marked = new boolean[G.V()];
validateVertex(s);
// to be able to iterate over each adjacency list, keeping track of which
// vertex in each adjacency list needs to be explored next
Iterator