001// Exercise 4.1.13 (Solution published at http://algs4.cs.princeton.edu/) 002package algs41; 003import stdlib.*; 004import algs13.Queue; 005import algs13.Stack; 006/* *********************************************************************** 007 * Compilation: javac BreadthFirstPaths.java 008 * Execution: java BreadthFirstPaths G s 009 * Dependencies: Graph.java Queue.java Stack.java StdOut.java 010 * Data files: http://algs4.cs.princeton.edu/41undirected/tinyCG.txt 011 * 012 * Run breadth first search on an undirected graph. 013 * Runs in O(E + V) time. 014 * 015 * % java Graph tinyCG.txt 016 * 6 8 017 * 0: 2 1 5 018 * 1: 0 2 019 * 2: 0 1 3 4 020 * 3: 5 4 2 021 * 4: 3 2 022 * 5: 3 0 023 * 024 * % java BreadthFirstPaths tinyCG.txt 0 025 * 0 to 0 (0): 0 026 * 0 to 1 (1): 0-1 027 * 0 to 2 (1): 0-2 028 * 0 to 3 (2): 0-2-3 029 * 0 to 4 (2): 0-2-4 030 * 0 to 5 (1): 0-5 031 * 032 *************************************************************************/ 033 034public class BreadthFirstPaths { 035 private static final int INFINITY = Integer.MAX_VALUE; 036 private final boolean[] marked; // marked[v] = is there an s-v path 037 private final int[] edgeTo; // edgeTo[v] = previous edge on shortest s-v path 038 private final int[] distTo; // distTo[v] = number of edges shortest s-v path 039 040 // single source 041 public BreadthFirstPaths(Graph G, int s) { 042 marked = new boolean[G.V()]; 043 distTo = new int[G.V()]; 044 edgeTo = new int[G.V()]; 045 bfs(G, s); 046 047 assert check(G, s); 048 } 049 050 // multiple sources 051 public BreadthFirstPaths(Graph G, Iterable<Integer> sources) { 052 marked = new boolean[G.V()]; 053 distTo = new int[G.V()]; 054 edgeTo = new int[G.V()]; 055 for (int v = 0; v < G.V(); v++) distTo[v] = INFINITY; 056 bfs(G, sources); 057 } 058 059 060 // BFS from single soruce 061 private void bfs(Graph G, int s) { 062 Queue<Integer> q = new Queue<>(); 063 for (int v = 0; v < G.V(); v++) distTo[v] = INFINITY; 064 distTo[s] = 0; 065 marked[s] = true; 066 q.enqueue(s); 067 068 while (!q.isEmpty()) { 069 int v = q.dequeue(); 070 for (int w : G.adj(v)) { 071 if (!marked[w]) { 072 edgeTo[w] = v; 073 distTo[w] = distTo[v] + 1; 074 marked[w] = true; 075 q.enqueue(w); 076 } 077 } 078 } 079 } 080 081 // BFS from multiple sources 082 private void bfs(Graph G, Iterable<Integer> sources) { 083 Queue<Integer> q = new Queue<>(); 084 for (int s : sources) { 085 marked[s] = true; 086 distTo[s] = 0; 087 q.enqueue(s); 088 } 089 while (!q.isEmpty()) { 090 int v = q.dequeue(); 091 for (int w : G.adj(v)) { 092 if (!marked[w]) { 093 edgeTo[w] = v; 094 distTo[w] = distTo[v] + 1; 095 marked[w] = true; 096 q.enqueue(w); 097 } 098 } 099 } 100 } 101 102 // is there a path between s (or sources) and v? 103 public boolean hasPathTo(int v) { 104 return marked[v]; 105 } 106 107 // length of shortest path between s (or sources) and v 108 public int distTo(int v) { 109 return distTo[v]; 110 } 111 112 // shortest path bewteen s (or sources) and v; null if no such path 113 public Iterable<Integer> pathTo(int v) { 114 if (!hasPathTo(v)) return null; 115 Stack<Integer> path = new Stack<>(); 116 int x; 117 for (x = v; distTo[x] != 0; x = edgeTo[x]) 118 path.push(x); 119 path.push(x); 120 return path; 121 } 122 123 124 // check optimality conditions for single source 125 private boolean check(Graph G, int s) { 126 127 // check that the distance of s = 0 128 if (distTo[s] != 0) { 129 StdOut.println("distance of source " + s + " to itself = " + distTo[s]); 130 return false; 131 } 132 133 // check that for each edge v-w dist[w] <= dist[v] + 1 134 // provided v is reachable from s 135 for (int v = 0; v < G.V(); v++) { 136 for (int w : G.adj(v)) { 137 if (hasPathTo(v) != hasPathTo(w)) { 138 StdOut.println("edge " + v + "-" + w); 139 StdOut.println("hasPathTo(" + v + ") = " + hasPathTo(v)); 140 StdOut.println("hasPathTo(" + w + ") = " + hasPathTo(w)); 141 return false; 142 } 143 if (hasPathTo(v) && (distTo[w] > distTo[v] + 1)) { 144 StdOut.println("edge " + v + "-" + w); 145 StdOut.println("distTo[" + v + "] = " + distTo[v]); 146 StdOut.println("distTo[" + w + "] = " + distTo[w]); 147 return false; 148 } 149 } 150 } 151 152 // check that v = edgeTo[w] satisfies distTo[w] + distTo[v] + 1 153 // provided v is reachable from s 154 for (int w = 0; w < G.V(); w++) { 155 if (!hasPathTo(w) || w == s) continue; 156 int v = edgeTo[w]; 157 if (distTo[w] != distTo[v] + 1) { 158 StdOut.println("shortest path edge " + v + "-" + w); 159 StdOut.println("distTo[" + v + "] = " + distTo[v]); 160 StdOut.println("distTo[" + w + "] = " + distTo[w]); 161 return false; 162 } 163 } 164 165 return true; 166 } 167 168 169 // test client 170 public static void main(String[] args) { 171 //args = new String [] { "data/tinyAG.txt", "0"}; 172 args = new String [] { "data/tinyG.txt", "0" }; 173 In in = new In(args[0]); 174 Graph G = GraphGenerator.fromIn (in); 175 StdOut.println(G); 176 177 int s = Integer.parseInt(args[1]); 178 BreadthFirstPaths bfs = new BreadthFirstPaths(G, s); 179 180 for (int v = 0; v < G.V(); v++) { 181 if (bfs.hasPathTo(v)) { 182 StdOut.format("%d to %d (%d): ", s, v, bfs.distTo(v)); 183 for (int x : bfs.pathTo(v)) { 184 if (x == s) StdOut.print(x); 185 else StdOut.print("-" + x); 186 } 187 StdOut.println(); 188 } 189 190 else { 191 StdOut.format("%d to %d (-): not connected\n", s, v); 192 } 193 194 } 195 } 196 197 198}