001package algs41; 002import stdlib.*; 003import algs13.Stack; 004/* *********************************************************************** 005 * Compilation: javac DepthFirstPaths.java 006 * Execution: java DepthFirstPaths G s 007 * Dependencies: Graph.java Stack.java StdOut.java 008 * Data files: http://algs4.cs.princeton.edu/41undirected/tinyCG.txt 009 * 010 * Run depth first search on an undirected graph. 011 * Runs in O(E + V) time. 012 * 013 * % java Graph tinyCG.txt 014 * 6 8 015 * 0: 2 1 5 016 * 1: 0 2 017 * 2: 0 1 3 4 018 * 3: 5 4 2 019 * 4: 3 2 020 * 5: 3 0 021 * 022 * % java DepthFirstPaths tinyCG.txt 0 023 * 0 to 0: 0 024 * 0 to 1: 0-2-1 025 * 0 to 2: 0-2 026 * 0 to 3: 0-2-3 027 * 0 to 4: 0-2-3-4 028 * 0 to 5: 0-2-3-5 029 * 030 *************************************************************************/ 031 032public class DepthFirstPaths { 033 private final boolean[] marked; // marked[v] = is there an s-v path? 034 private final int[] edgeTo; // edgeTo[v] = last edge on s-v path 035 private final int s; // source vertex 036 037 public DepthFirstPaths(Graph G, int s) { 038 this.s = s; 039 edgeTo = new int[G.V()]; 040 marked = new boolean[G.V()]; 041 dfsLoop (G, s); 042 } 043 044 // depth first search from v 045 private void dfs(Graph G, int v) { 046 //StdOut.format ("visited %d\n", v); 047 marked[v] = true; 048 for (int w : G.adj(v)) { 049 if (!marked[w]) { 050 edgeTo[w] = v; 051 dfs(G, w); 052 } 053 } 054 } 055 private void dfsLoop(Graph G, int s) { 056 Stack<Integer> stack = new Stack<>(); 057 stack.push(s); 058 059 while (!stack.isEmpty()) { 060 int v = stack.pop(); 061 marked[v] = true; // For DFS, mark as you pop 062 for (int w : G.adj(v)) { 063 if (!marked[w]) { 064 edgeTo[w] = v; 065 stack.push(w); 066 } 067 } 068 } 069 } 070 private void dfsLoopReversed(Graph G, int s) { 071 Stack<Integer> stack = new Stack<>(); 072 stack.push(s); 073 074 while (!stack.isEmpty()) { 075 int v = stack.pop(); 076 marked[v] = true; 077 078 // tmp is used to get the vertices in the same order as used by the recursive version 079 // tmp is not necessary, if you don't care about the order 080 Stack<Integer> tmp = new Stack<>(); 081 for (int w : G.adj(v)) { 082 if (!marked[w]) { 083 edgeTo[w] = v; 084 tmp.push(w); 085 } 086 } 087 while (!tmp.isEmpty ()) 088 stack.push (tmp.pop ()); 089 } 090 } 091 092 093 094 // is there a path between s and w? 095 public boolean hasPathTo(int w) { 096 return marked[w]; 097 } 098 099 // return a path between s to w; null if no such path 100 public Iterable<Integer> pathTo(int w) { 101 if (!hasPathTo(w)) return null; 102 Stack<Integer> path = new Stack<>(); 103 for (int x = w; x != s; x = edgeTo[x]) 104 path.push(x); 105 path.push(s); 106 return path; 107 } 108 109 public static void main(String[] args) { 110 args = new String [] { "data/tinyG.txt", "0" }; 111 //args = new String [] { "data/tinyCG.txt", "0" }; 112 113 In in = new In(args[0]); 114 Graph G = GraphGenerator.fromIn (in); 115 StdOut.println (G); 116 G.toGraphviz ("graph"); 117 118 int s = Integer.parseInt(args[1]); 119 DepthFirstPaths dfs = new DepthFirstPaths(G, s); 120 121 for (int v = 0; v < G.V(); v++) { 122 if (dfs.hasPathTo(v)) { 123 StdOut.format("%d to %d: ", s, v); 124 for (int x : dfs.pathTo(v)) { 125 if (x == s) StdOut.print(x); 126 else StdOut.print("-" + x); 127 } 128 StdOut.println(); 129 } 130 131 else { 132 StdOut.format("%d to %d: not connected\n", s, v); 133 } 134 135 } 136 } 137 138}