001package algs42; 002import stdlib.*; 003import algs13.Queue; 004import algs13.Stack; 005/* *********************************************************************** 006 * Compilation: javac BreadthFirstDirectedPaths.java 007 * Execution: java BreadthFirstDirectedPaths V E 008 * Dependencies: Digraph.java Queue.java Stack.java 009 * 010 * Run breadth first search on a digraph. 011 * Runs in O(E + V) time. 012 * 013 * % java BreadthFirstDirectedPaths tinyDG.txt 3 014 * 3 to 0 (2): 3->2->0 015 * 3 to 1 (3): 3->2->0->1 016 * 3 to 2 (1): 3->2 017 * 3 to 3 (0): 3 018 * 3 to 4 (2): 3->5->4 019 * 3 to 5 (1): 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 BreadthFirstDirectedPaths { 031 private static int INFINITY = Integer.MAX_VALUE; 032 private boolean[] marked; // marked[v] = is there an s->v path? 033 private int[] edgeTo; // edgeTo[v] = last edge on shortest s->v path 034 private int[] distTo; // distTo[v] = length of shortest s->v path 035 036 // single source 037 public BreadthFirstDirectedPaths(Digraph G, int s) { 038 marked = new boolean[G.V()]; 039 distTo = new int[G.V()]; 040 edgeTo = new int[G.V()]; 041 for (int v = 0; v < G.V(); v++) distTo[v] = INFINITY; 042 bfs(G, s); 043 } 044 045 // multiple sources 046 public BreadthFirstDirectedPaths(Digraph G, Iterable<Integer> sources) { 047 marked = new boolean[G.V()]; 048 distTo = new int[G.V()]; 049 edgeTo = new int[G.V()]; 050 for (int v = 0; v < G.V(); v++) distTo[v] = INFINITY; 051 bfs(G, sources); 052 } 053 054 // BFS from single source 055 private void bfs(Digraph G, int s) { 056 Queue<Integer> q = new Queue<>(); 057 marked[s] = true; 058 distTo[s] = 0; 059 q.enqueue(s); 060 while (!q.isEmpty()) { 061 int v = q.dequeue(); 062 for (int w : G.adj(v)) { 063 if (!marked[w]) { 064 edgeTo[w] = v; 065 distTo[w] = distTo[v] + 1; 066 marked[w] = true; // for BFS, mark as you enqueue 067 q.enqueue(w); 068 } 069 } 070 } 071 } 072 073 // BFS from multiple sources 074 private void bfs(Digraph G, Iterable<Integer> sources) { 075 Queue<Integer> q = new Queue<>(); 076 for (int s : sources) { 077 marked[s] = true; 078 distTo[s] = 0; 079 q.enqueue(s); 080 } 081 while (!q.isEmpty()) { 082 int v = q.dequeue(); 083 for (int w : G.adj(v)) { 084 if (!marked[w]) { 085 edgeTo[w] = v; 086 distTo[w] = distTo[v] + 1; 087 marked[w] = true; 088 q.enqueue(w); 089 } 090 } 091 } 092 } 093 094 // length of shortest path from s (or sources) to v 095 public int distTo(int v) { 096 return distTo[v]; 097 } 098 099 // is there a directed path from s (or sources) to v? 100 public boolean hasPathTo(int v) { 101 return marked[v]; 102 } 103 104 // shortest path from s (or sources) to v; null if no such path 105 public Iterable<Integer> pathTo(int v) { 106 if (!hasPathTo(v)) return null; 107 Stack<Integer> path = new Stack<>(); 108 int x; 109 for (x = v; distTo[x] != 0; x = edgeTo[x]) 110 path.push(x); 111 path.push(x); 112 return path; 113 } 114 115 public static void main(String[] args) { 116 args = new String[] { "data/tinyDG.txt", "3" }; 117 118 In in = new In(args[0]); 119 Digraph G = DigraphGenerator.fromIn(in); 120 // StdOut.println(G); 121 122 int s = Integer.parseInt(args[1]); 123 BreadthFirstDirectedPaths bfs = new BreadthFirstDirectedPaths(G, s); 124 125 for (int v = 0; v < G.V(); v++) { 126 if (bfs.hasPathTo(v)) { 127 StdOut.format("%d to %d (%d): ", s, v, bfs.distTo(v)); 128 for (int x : bfs.pathTo(v)) { 129 if (x == s) StdOut.print(x); 130 else StdOut.print("->" + x); 131 } 132 StdOut.println(); 133 } 134 135 else { 136 StdOut.format("%d to %d (-): not connected\n", s, v); 137 } 138 139 } 140 } 141 142 143}