Below is the syntax highlighted version of DepthFirstSearch.java.
/****************************************************************************** * Compilation: javac DepthFirstSearch.java * Execution: java DepthFirstSearch filename.txt s * Dependencies: Graph.java StdOut.java * Data files: https://algs4.cs.princeton.edu/41graph/tinyG.txt * https://algs4.cs.princeton.edu/41graph/mediumG.txt * * Run depth first search on an undirected graph. * Runs in O(E + V) time. * * % java DepthFirstSearch tinyG.txt 0 * 0 1 2 3 4 5 6 * NOT connected * * % java DepthFirstSearch tinyG.txt 9 * 9 10 11 12 * NOT connected * ******************************************************************************/ package edu.princeton.cs.algs4; /** * The {@code DepthFirstSearch} class represents a data type for * determining the vertices connected to a given source vertex <em>s</em> * in an undirected graph. For versions that find the paths, see * {@link DepthFirstPaths} and {@link BreadthFirstPaths}. * <p> * This implementation uses depth-first search. * See {@link NonrecursiveDFS} for a non-recursive version. * 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 graph). * <p> * For additional documentation, see * <a href="https://algs4.cs.princeton.edu/41graph">Section 4.1</a> * of <i>Algorithms, 4th Edition</i> by Robert Sedgewick and Kevin Wayne. * * @author Robert Sedgewick * @author Kevin Wayne */ public class DepthFirstSearch { private boolean[] marked; // marked[v] = is there an s-v path? private int count; // number of vertices connected to s /** * Computes the vertices in graph {@code G} that are * connected to the source vertex {@code s}. * @param G the graph * @param s the source vertex * @throws IllegalArgumentException unless {@code 0 <= s < V} */ public DepthFirstSearch(Graph G, int s) { marked = new boolean[G.V()]; validateVertex(s); dfs(G, s); } // depth first search from v private void dfs(Graph G, int v) { count++; marked[v] = true; for (int w : G.adj(v)) { if (!marked[w]) { dfs(G, w); } } } /** * Is there a path between the source vertex {@code s} and vertex {@code v}? * @param v the vertex * @return {@code true} if there is a path, {@code false} otherwise * @throws IllegalArgumentException unless {@code 0 <= v < V} */ public boolean marked(int v) { validateVertex(v); return marked[v]; } /** * Returns the number of vertices connected to the source vertex {@code s}. * @return the number of vertices connected to the source vertex {@code s} */ public int count() { return count; } // 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)); } /** * Unit tests the {@code DepthFirstSearch} data type. * * @param args the command-line arguments */ public static void main(String[] args) { In in = new In(args[0]); Graph G = new Graph(in); int s = Integer.parseInt(args[1]); DepthFirstSearch search = new DepthFirstSearch(G, s); for (int v = 0; v < G.V(); v++) { if (search.marked(v)) StdOut.print(v + " "); } StdOut.println(); if (search.count() != G.V()) StdOut.println("NOT connected"); else StdOut.println("connected"); } } /****************************************************************************** * 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. ******************************************************************************/