001package algs42; 002import stdlib.*; 003import algs13.Bag; 004/* *********************************************************************** 005 * Compilation: javac DirectedDFS.java 006 * Execution: java DirectedDFS V E 007 * Dependencies: Digraph.java Bag.java In.java StdOut.java 008 * Data files: http://www.cs.princeton.edu/algs4/42directed/tinyDG.txt 009 * 010 * Determine single-source or multiple-source reachability in a digraph 011 * using depth first search. 012 * Runs in O(E + V) time. 013 * 014 * % java DirectedDFS tinyDG.txt 1 015 * 1 016 * 017 * % java DirectedDFS tinyDG.txt 2 018 * 0 1 2 3 4 5 019 * 020 * % java DirectedDFS tinyDG.txt 1 2 6 021 * 0 1 2 3 4 5 6 9 10 11 12 022 * 023 *************************************************************************/ 024 025public class DirectedDFS { 026 private final boolean[] marked; // marked[v] = true if v is reachable 027 // from source (or sources) 028 029 // single-source reachability 030 public DirectedDFS(Digraph G, int s) { 031 marked = new boolean[G.V()]; 032 dfs(G, s); 033 } 034 035 // multiple-source reachability 036 public DirectedDFS(Digraph G, Iterable<Integer> sources) { 037 marked = new boolean[G.V()]; 038 for (int v : sources) 039 dfs(G, v); 040 } 041 042 private void dfs(Digraph G, int v) { 043 marked[v] = true; 044 for (int w : G.adj(v)) { 045 if (!marked[w]) dfs(G, w); 046 } 047 } 048 049 // is there a directed path from the source (or sources) to v? 050 public boolean marked(int v) { 051 return marked[v]; 052 } 053 054 // test client 055 public static void main(String[] args) { 056 //args = new String[] { "data/tinyDG.txt", "1" }; 057 args = new String[] { "data/tinyDG.txt", "2" }; 058 //args = new String[] { "data/tinyDG.txt", "1", "2", "6" }; 059 060 // read in digraph from command-line argument 061 In in = new In(args[0]); 062 Digraph G = DigraphGenerator.fromIn(in); 063 064 // read in sources from command-line arguments 065 Bag<Integer> sources = new Bag<>(); 066 for (int i = 1; i < args.length; i++) { 067 int s = Integer.parseInt(args[i]); 068 sources.add(s); 069 } 070 071 // multiple-source reachability 072 DirectedDFS dfs = new DirectedDFS(G, sources); 073 074 // print out vertices reachable from sources 075 for (int v = 0; v < G.V(); v++) { 076 if (dfs.marked(v)) StdOut.print(v + " "); 077 } 078 StdOut.println(); 079 } 080 081}