Below is the syntax highlighted version of BreadthFirstDirectedPaths.java.
/****************************************************************************** * Compilation: javac BreadthFirstDirectedPaths.java * Execution: java BreadthFirstDirectedPaths digraph.txt s * Dependencies: Digraph.java Queue.java Stack.java * Data files: https://algs4.cs.princeton.edu/42digraph/tinyDG.txt * https://algs4.cs.princeton.edu/42digraph/mediumDG.txt * https://algs4.cs.princeton.edu/42digraph/largeDG.txt * * Run breadth-first search on a digraph. * Runs in O(E + V) time. * * % java BreadthFirstDirectedPaths tinyDG.txt 3 * 3 to 0 (2): 3->2->0 * 3 to 1 (3): 3->2->0->1 * 3 to 2 (1): 3->2 * 3 to 3 (0): 3 * 3 to 4 (2): 3->5->4 * 3 to 5 (1): 3->5 * 3 to 6 (-): not connected * 3 to 7 (-): not connected * 3 to 8 (-): not connected * 3 to 9 (-): not connected * 3 to 10 (-): not connected * 3 to 11 (-): not connected * 3 to 12 (-): not connected * ******************************************************************************/ package edu.princeton.cs.algs4; /** * The {@code BreadthDirectedFirstPaths} class represents a data type for * finding shortest paths (number of edges) from a source vertex <em>s</em> * (or set of source vertices) to every other vertex in the digraph. * <p> * This implementation uses breadth-first search. * The constructor takes Θ(<em>V</em> + <em>E</em>) time in the * worst case, where <em>V</em> is the number of vertices and <em>E</em> is * the number of edges. * Each instance method takes Θ(1) time. * It uses Θ(<em>V</em>) extra space (not including the digraph). * <p> * For additional documentation, * see <a href="https://algs4.cs.princeton.edu/42digraph">Section 4.2</a> of * <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne. * * @author Robert Sedgewick * @author Kevin Wayne */ public class BreadthFirstDirectedPaths { private static final int INFINITY = Integer.MAX_VALUE; private boolean[] marked; // marked[v] = is there an s->v path? private int[] edgeTo; // edgeTo[v] = last edge on shortest s->v path private int[] distTo; // distTo[v] = length of shortest s->v path /** * Computes the shortest path from {@code s} and every other vertex in graph {@code G}. * @param G the digraph * @param s the source vertex * @throws IllegalArgumentException unless {@code 0 <= v < V} */ public BreadthFirstDirectedPaths(Digraph G, int s) { marked = new boolean[G.V()]; distTo = new int[G.V()]; edgeTo = new int[G.V()]; for (int v = 0; v < G.V(); v++) distTo[v] = INFINITY; validateVertex(s); bfs(G, s); } /** * Computes the shortest path from any one of the source vertices in {@code sources} * to every other vertex in graph {@code G}. * @param G the digraph * @param sources the source vertices * @throws IllegalArgumentException if {@code sources} is {@code null} * @throws IllegalArgumentException if {@code sources} contains no vertices * @throws IllegalArgumentException unless each vertex {@code v} in * {@code sources} satisfies {@code 0 <= v < V} */ public BreadthFirstDirectedPaths(Digraph G, Iterable<Integer> sources) { marked = new boolean[G.V()]; distTo = new int[G.V()]; edgeTo = new int[G.V()]; for (int v = 0; v < G.V(); v++) distTo[v] = INFINITY; validateVertices(sources); bfs(G, sources); } // BFS from single source private void bfs(Digraph G, int s) { Queue<Integer> q = new Queue<Integer>(); marked[s] = true; distTo[s] = 0; q.enqueue(s); while (!q.isEmpty()) { int v = q.dequeue(); for (int w : G.adj(v)) { if (!marked[w]) { edgeTo[w] = v; distTo[w] = distTo[v] + 1; marked[w] = true; q.enqueue(w); } } } } // BFS from multiple sources private void bfs(Digraph G, Iterable<Integer> sources) { Queue<Integer> q = new Queue<Integer>(); for (int s : sources) { marked[s] = true; distTo[s] = 0; q.enqueue(s); } while (!q.isEmpty()) { int v = q.dequeue(); for (int w : G.adj(v)) { if (!marked[w]) { edgeTo[w] = v; distTo[w] = distTo[v] + 1; marked[w] = true; q.enqueue(w); } } } } /** * Is there a directed path from the source {@code s} (or sources) to vertex {@code v}? * @param v the vertex * @return {@code true} if there is a directed path, {@code false} otherwise * @throws IllegalArgumentException unless {@code 0 <= v < V} */ public boolean hasPathTo(int v) { validateVertex(v); return marked[v]; } /** * Returns the number of edges in a shortest path from the source {@code s} * (or sources) to vertex {@code v}? * @param v the vertex * @return the number of edges in such a shortest path * (or {@code Integer.MAX_VALUE} if there is no such path) * @throws IllegalArgumentException unless {@code 0 <= v < V} */ public int distTo(int v) { validateVertex(v); return distTo[v]; } /** * Returns a shortest path from {@code s} (or sources) to {@code v}, or * {@code null} if no such path. * @param v the vertex * @return the sequence of vertices on a shortest path, as an Iterable * @throws IllegalArgumentException unless {@code 0 <= v < V} */ public Iterable<Integer> pathTo(int v) { validateVertex(v); if (!hasPathTo(v)) return null; Stack<Integer> path = new Stack<Integer>(); int x; for (x = v; distTo[x] != 0; x = edgeTo[x]) path.push(x); path.push(x); return path; } // throw an IllegalArgumentException unless {@code 0 <= v < V} private void validateVertex(int v) { int V = marked.length; if (v < 0 || v >= V) throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1)); } // throw an IllegalArgumentException if vertices is null, has zero vertices, // or has a vertex not between 0 and V-1 private void validateVertices(Iterable<Integer> vertices) { if (vertices == null) { throw new IllegalArgumentException("argument is null"); } int vertexCount = 0; for (Integer v : vertices) { vertexCount++; if (v == null) { throw new IllegalArgumentException("vertex is null"); } validateVertex(v); } if (vertexCount == 0) { throw new IllegalArgumentException("zero vertices"); } } /** * Unit tests the {@code BreadthFirstDirectedPaths} data type. * * @param args the command-line arguments */ public static void main(String[] args) { In in = new In(args[0]); Digraph G = new Digraph(in); // StdOut.println(G); int s = Integer.parseInt(args[1]); BreadthFirstDirectedPaths bfs = new BreadthFirstDirectedPaths(G, s); for (int v = 0; v < G.V(); v++) { if (bfs.hasPathTo(v)) { StdOut.printf("%d to %d (%d): ", s, v, bfs.distTo(v)); for (int x : bfs.pathTo(v)) { if (x == s) StdOut.print(x); else StdOut.print("->" + x); } StdOut.println(); } else { StdOut.printf("%d to %d (-): not connected\n", s, v); } } } } /****************************************************************************** * Copyright 2002-2022, Robert Sedgewick and Kevin Wayne. * * This file is part of algs4.jar, which accompanies the textbook * * Algorithms, 4th edition by Robert Sedgewick and Kevin Wayne, * Addison-Wesley Professional, 2011, ISBN 0-321-57351-X. * http://algs4.cs.princeton.edu * * * algs4.jar is free software: you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation, either version 3 of the License, or * (at your option) any later version. * * algs4.jar is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with algs4.jar. If not, see http://www.gnu.org/licenses. ******************************************************************************/