Below is the syntax highlighted version of DirectedDFS.java.
/****************************************************************************** * 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 * ******************************************************************************/ package edu.princeton.cs.algs4; /** * The {@code DirectedDFS} class represents a data type for * determining the vertices reachable from a given source vertex <em>s</em> * (or set of source vertices) in a digraph. For versions that find the paths, * see {@link DepthFirstDirectedPaths} and {@link BreadthFirstDirectedPaths}. * <p> * This implementation uses depth-first search. * The constructor takes time proportional to <em>V</em> + <em>E</em> * (in the worst case), * where <em>V</em> is the number of vertices and <em>E</em> is the number of edges. * Each instance method takes Θ(1) time. * It uses Θ(<em>V</em>) extra space (not including the digraph). * <p> * For additional documentation, * see <a href="https://algs4.cs.princeton.edu/42digraph">Section 4.2</a> of * <i>Algorithms, 4th Edition</i> 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<Integer> sources) { marked = new boolean[G.V()]; validateVertices(sources); for (int v : sources) { if (!marked[v]) dfs(G, v); } } private void dfs(Digraph G, int v) { count++; marked[v] = true; for (int w : G.adj(v)) { if (!marked[w]) dfs(G, w); } } /** * Is there a directed path from the source vertex (or any * of the source vertices) and vertex {@code v}? * @param v the vertex * @return {@code true} if there is a directed path, {@code false} otherwise * @throws IllegalArgumentException unless {@code 0 <= v < V} */ public boolean marked(int v) { validateVertex(v); return marked[v]; } /** * Returns the number of vertices reachable from the source vertex * (or source vertices). * @return the number of vertices reachable from the source vertex * (or source vertices) */ public int count() { return count; } // throw an IllegalArgumentException unless {@code 0 <= v < V} private void validateVertex(int v) { int V = marked.length; if (v < 0 || v >= V) throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1)); } // throw an IllegalArgumentException if vertices is null, has zero vertices, // or has a vertex not between 0 and V-1 private void validateVertices(Iterable<Integer> vertices) { if (vertices == null) { throw new IllegalArgumentException("argument is null"); } int vertexCount = 0; for (Integer v : vertices) { vertexCount++; if (v == null) { throw new IllegalArgumentException("vertex is null"); } validateVertex(v); } if (vertexCount == 0) { throw new IllegalArgumentException("zero vertices"); } } /** * Unit tests the {@code DirectedDFS} data type. * * @param args the command-line arguments */ public static void main(String[] args) { // read in digraph from command-line argument In in = new In(args[0]); Digraph G = new Digraph(in); // read in sources from command-line arguments Bag<Integer> sources = new Bag<Integer>(); for (int i = 1; i < args.length; i++) { int s = Integer.parseInt(args[i]); sources.add(s); } // multiple-source reachability DirectedDFS dfs = new DirectedDFS(G, sources); // print out vertices reachable from sources for (int v = 0; v < G.V(); v++) { if (dfs.marked(v)) StdOut.print(v + " "); } StdOut.println(); } } /****************************************************************************** * Copyright 2002-2022, Robert Sedgewick and Kevin Wayne. * * This file is part of algs4.jar, which accompanies the textbook * * Algorithms, 4th edition by Robert Sedgewick and Kevin Wayne, * Addison-Wesley Professional, 2011, ISBN 0-321-57351-X. * http://algs4.cs.princeton.edu * * * algs4.jar is free software: you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation, either version 3 of the License, or * (at your option) any later version. * * algs4.jar is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with algs4.jar. If not, see http://www.gnu.org/licenses. ******************************************************************************/