001package algs42; 002import stdlib.*; 003import algs13.Stack; 004/* *********************************************************************** 005 * Compilation: javac DepthFirstDirectedPaths.java 006 * Execution: java DepthFirstDirectedPaths G s 007 * Dependencies: Digraph.java Stack.java 008 * 009 * Determine reachability in a digraph from a given vertex using 010 * depth first search. 011 * Runs in O(E + V) time. 012 * 013 * % tinyDG.txt 3 014 * 3 to 0: 3-5-4-2-0 015 * 3 to 1: 3-5-4-2-0-1 016 * 3 to 2: 3-5-4-2 017 * 3 to 3: 3 018 * 3 to 4: 3-5-4 019 * 3 to 5: 3-5 020 * 3 to 6: not connected 021 * 3 to 7: not connected 022 * 3 to 8: not connected 023 * 3 to 9: not connected 024 * 3 to 10: not connected 025 * 3 to 11: not connected 026 * 3 to 12: not connected 027 * 028 *************************************************************************/ 029 030public class DepthFirstDirectedPaths { 031 private final boolean[] marked; // marked[v] = true if v is reachable from s 032 private final int[] edgeTo; // edgeTo[v] = last edge on path from s to v 033 private final int s; // source vertex 034 035 // single source 036 public DepthFirstDirectedPaths(Digraph G, int s) { 037 marked = new boolean[G.V()]; 038 edgeTo = new int[G.V()]; 039 this.s = s; 040 dfs(G, s); 041 } 042 043 044 private void dfs(Digraph G, int v) { 045 marked[v] = true; 046 for (int w : G.adj(v)) { 047 if (!marked[w]) { 048 edgeTo[w] = v; 049 dfs(G, w); 050 } 051 } 052 } 053 054 // is there a directed path from s to v? 055 public boolean hasPathTo(int v) { 056 return marked[v]; 057 } 058 059 // return path from s to v; null if no such path 060 public Iterable<Integer> pathTo(int v) { 061 if (!hasPathTo(v)) return null; 062 Stack<Integer> path = new Stack<>(); 063 for (int x = v; x != s; x = edgeTo[x]) 064 path.push(x); 065 path.push(s); 066 return path; 067 } 068 069 public static void main(String[] args) { 070 args = new String[] { "data/tinyDG.txt", "3" }; 071 072 In in = new In(args[0]); 073 Digraph G = DigraphGenerator.fromIn(in); 074 // StdOut.println(G); 075 076 int s = Integer.parseInt(args[1]); 077 DepthFirstDirectedPaths dfs = new DepthFirstDirectedPaths(G, s); 078 079 for (int v = 0; v < G.V(); v++) { 080 if (dfs.hasPathTo(v)) { 081 StdOut.format("%d to %d: ", s, v); 082 for (int x : dfs.pathTo(v)) { 083 if (x == s) StdOut.print(x); 084 else StdOut.print("-" + x); 085 } 086 StdOut.println(); 087 } 088 089 else { 090 StdOut.format("%d to %d: not connected\n", s, v); 091 } 092 093 } 094 } 095 096}