/****************************************************************************** * Compilation: javac DirectedDFS.java * Execution: java DirectedDFS digraph.txt s * Dependencies: Digraph.java Bag.java In.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 * * Determine single-source or multiple-source reachability in a digraph * using depth first search. * Runs in O(E + V) time. * * % java DirectedDFS tinyDG.txt 1 * 1 * * % java DirectedDFS tinyDG.txt 2 * 0 1 2 3 4 5 * * % java DirectedDFS tinyDG.txt 1 2 6 * 0 1 2 3 4 5 6 8 9 10 11 12 * ******************************************************************************/ /** * The {@code 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 {@link DepthFirstDirectedPaths} and {@link 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.
*
* @author Robert Sedgewick
* @author Kevin Wayne
*/
public class DirectedDFS {
private boolean[] marked; // marked[v] = true iff v is reachable from source(s)
private int count; // number of vertices reachable from source(s)
/**
* Computes the vertices in digraph {@code G} that are
* reachable from the source vertex {@code s}.
* @param G the digraph
* @param s the source vertex
* @throws IllegalArgumentException unless {@code 0 <= s < V}
*/
public DirectedDFS(Digraph G, int s) {
marked = new boolean[G.V()];
validateVertex(s);
dfs(G, s);
}
/**
* Computes the vertices in digraph {@code G} that are
* connected to any of the source vertices {@code sources}.
* @param G the graph
* @param sources the source vertices
* @throws IllegalArgumentException if {@code sources} is {@code null}
* @throws IllegalArgumentException if {@code sources} contains no vertices
* @throws IllegalArgumentException unless {@code 0 <= s < V}
* for each vertex {@code s} in {@code sources}
*/
public DirectedDFS(Digraph G, Iterable