|
| 1 | +/** |
| 2 | + * Run depth first search on an undirected graph. |
| 3 | + * Runs in O(E + V) time. |
| 4 | + * |
| 5 | + */ |
| 6 | +public class DepthFirstPaths { |
| 7 | + private boolean[] marked; // marked[v] = is there an s-v path? |
| 8 | + private int[] edgeTo; // edgeTo[v] = last edge on s-v path |
| 9 | + private final int s; // source vertex |
| 10 | + |
| 11 | + // Computes a path between `s` and every other vertex in graph `G` |
| 12 | + public DepthFirstPaths(Graph G, int s) { |
| 13 | + this.s = s; |
| 14 | + edgeTo = new int[G.V()]; |
| 15 | + marked = new boolean[G.V()]; |
| 16 | + validateVertex(s); |
| 17 | + dfs(G, s); |
| 18 | + } |
| 19 | + |
| 20 | + // depth first search from v |
| 21 | + private void dfs(Graph G, int v) { |
| 22 | + marked[v] = true; |
| 23 | + for(int w: G.adj(v)) { |
| 24 | + if(!marked[w]) { |
| 25 | + edgeTo[w] = v; |
| 26 | + dfs(G, w); |
| 27 | + } |
| 28 | + } |
| 29 | + } |
| 30 | + |
| 31 | + // is there a path between the source vertex `s` and vertex `v` |
| 32 | + public boolean hasPathTo(int v) { |
| 33 | + validateVertex(v); |
| 34 | + return marked[v]; |
| 35 | + } |
| 36 | + |
| 37 | + // Returns a path between the source vertex `s` and the vertex `v` |
| 38 | + // return null if no such path. |
| 39 | + public Iterable<Integer> pathTo(int v) { |
| 40 | + validateVertex(v); |
| 41 | + if(!hasPathTo(v)) |
| 42 | + return null; |
| 43 | + stack<Integer> path = new Stack<Integer>(); |
| 44 | + for(int x = v; x != s; x = edgeTo[x]) |
| 45 | + path.push(x); |
| 46 | + path.push(s); |
| 47 | + return path; |
| 48 | + } |
| 49 | + |
| 50 | + // throw an IllegalArgumentException unless `0 <= v < V` |
| 51 | + private void validateVertex(int v) { |
| 52 | + int V = marked.length; |
| 53 | + if(v < 0 || v >= V) |
| 54 | + throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V - 1)); |
| 55 | + } |
| 56 | + |
| 57 | + // tests |
| 58 | + public static void main(String[] args) { |
| 59 | + In in = new In(args[0]); |
| 60 | + Graph G = new Graph(in); |
| 61 | + int s = Integer.parseInt(args[1]); |
| 62 | + DepthFirstPaths dfs = new DepthFirstPaths(G, s); |
| 63 | + for(int v = 0; v < G.(); v++) { |
| 64 | + if(dfs.hasPathTo(v)) { |
| 65 | + StdOut.printf("%d to %d: ", s, v); |
| 66 | + for(int x:dfs.pathTo(v)) { |
| 67 | + if(x == s) |
| 68 | + StdOut.print(x); |
| 69 | + else |
| 70 | + StdOut.print("-" + x); |
| 71 | + } |
| 72 | + } else { |
| 73 | + StdOut.printf("%d to %d: not connected\n", s, v); |
| 74 | + } |
| 75 | + } |
| 76 | + } |
| 77 | +} |
0 commit comments