Graph class implementation /****************************************************************************** * Compilation: javac Graph.java * Execution: java Graph input.txt * Dependencies: Bag.java...

please follow instructions


Graph class implementation /****************************************************************************** * Compilation: javac Graph.java * Execution: java Graph input.txt * Dependencies: Bag.java Stack.java In.java StdOut.java * Data files: https://algs4.cs.princeton.edu/41graph/tinyG.txt * https://algs4.cs.princeton.edu/41graph/mediumG.txt * https://algs4.cs.princeton.edu/41graph/largeG.txt * * A graph, implemented using an array of sets. * Parallel edges and self-loops allowed. * * % java Graph tinyG.txt * 13 vertices, 13 edges * 0: 6 2 1 5 * 1: 0 * 2: 0 * 3: 5 4 * 4: 5 6 3 * 5: 3 4 0 * 6: 0 4 * 7: 8 * 8: 7 * 9: 11 10 12 * 10: 9 * 11: 9 12 * 12: 11 9 * * % java Graph mediumG.txt * 250 vertices, 1273 edges * 0: 225 222 211 209 204 202 191 176 163 160 149 114 97 80 68 59 58 49 44 24 15 * 1: 220 203 200 194 189 164 150 130 107 72 * 2: 141 110 108 86 79 51 42 18 14 * ... * ******************************************************************************/ package edu.princeton.cs.algs4; import java.util.NoSuchElementException; /** * The {@code Graph} class represents an undirected graph of vertices * named 0 through
V
– 1. * It supports the following two primary operations: add an edge to the graph, * iterate over all of the vertices adjacent to a vertex. It also provides * methods for returning the degree of a vertex, the number of vertices *
V
in the graph, and the number of edges
E
in the graph. * Parallel edges and self-loops are permitted. * By convention, a self-loop
v-v
appears in the * adjacency list of
v
twice and contributes two to the degree * of
v. *

* This implementation uses an
adjacency-lists representation, which * is a vertex-indexed array of {@link Bag} objects. * It uses Θ(E
+
V) space, where
E
is * the number of edges and
V
is the number of vertices. * All instance methods take Θ(1) time. (Though, iterating over * the vertices returned by {@link #adj(int)} takes time proportional * to the degree of the vertex.) * Constructing an empty graph with
V
vertices takes * Θ(V) time; constructing a graph with
E
edges * and
V
vertices takes Θ(E
+
V) time. *

* For additional documentation, see *
Section 4.1
* of
Algorithms, 4th Edition
by Robert Sedgewick and Kevin Wayne. * * @author Robert Sedgewick * @author Kevin Wayne */ public class Graph { private static final String NEWLINE = System.getProperty("line.separator"); private final int V; private int E; private Bag[] adj; /** * Initializes an empty graph with {@code V} vertices and 0 edges. * param V the number of vertices * * @param V number of vertices * @throws IllegalArgumentException if {@code V < 0}="" */="" public="" graph(int="" v)="" {="" if="" (v="">< 0)="" throw="" new="" illegalargumentexception("number="" of="" vertices="" must="" be="" non-negative");="" this.v="V;" this.e="0;" adj="">[]) new Bag[V]; for (int v = 0; v < v;="" v++)="" {="" adj[v]="new">(); } } /** * Initializes a graph from the specified input stream. * The format is the number of vertices
V, * followed by the number of edges
E, * followed by
E
pairs of vertices, with each entry separated by whitespace. * * @param in the input stream * @throws IllegalArgumentException if {@code in} is {@code null} * @throws IllegalArgumentException if the endpoints of any edge are not in prescribed range * @throws IllegalArgumentException if the number of vertices or edges is negative * @throws IllegalArgumentException if the input stream is in the wrong format */ public Graph(In in) { if (in == null) throw new IllegalArgumentException("argument is null"); try { this.V = in.readInt(); if (V < 0)="" throw="" new="" illegalargumentexception("number="" of="" vertices="" in="" a="" graph="" must="" be="" non-negative");="" adj="">[]) new Bag[V]; for (int v = 0; v < v;="" v++)="" {="" adj[v]="new">(); } int E = in.readInt(); if (E < 0)="" throw="" new="" illegalargumentexception("number="" of="" edges="" in="" a="" graph="" must="" be="" non-negative");="" for="" (int="" i="0;" i="">< e;="" i++)="" {="" int="" v="in.readInt();" int="" w="in.readInt();" validatevertex(v);="" validatevertex(w);="" addedge(v,="" w);="" }="" }="" catch="" (nosuchelementexception="" e)="" {="" throw="" new="" illegalargumentexception("invalid="" input="" format="" in="" graph="" constructor",="" e);="" }="" }="" **="" *="" initializes="" a="" new="" graph="" that="" is="" a="" deep="" copy="" of="" {@code="" g}.="" *="" *="" @param="" g="" the="" graph="" to="" copy="" *="" @throws="" illegalargumentexception="" if="" {@code="" g}="" is="" {@code="" null}="" */="" public="" graph(graph="" g)="" {="" this.v="G.V();" this.e="G.E();" if="" (v="">< 0)="" throw="" new="" illegalargumentexception("number="" of="" vertices="" must="" be="" non-negative");="" update="" adjacency="" lists="" adj="">[]) new Bag[V]; for (int v = 0; v < v;="" v++)="" {="" adj[v]="new">(); } for (int v = 0; v < g.v();="" v++)="" {="" reverse="" so="" that="" adjacency="" list="" is="" in="" same="" order="" as="" original=""> reverse = new Stack(); for (int w : G.adj[v]) { reverse.push(w); } for (int w : reverse) { adj[v].add(w); } } } /** * Returns the number of vertices in this graph. * * @return the number of vertices in this graph */ public int V() { return V; } /** * Returns the number of edges in this graph. * * @return the number of edges in this graph */ public int E() { return E; } // throw an IllegalArgumentException unless {@code 0 <= v="">< v}="" private="" void="" validatevertex(int="" v)="" {="" if="" (v="">< 0="" ||="" v="">= V) throw new IllegalArgumentException("vertex " + v + " is not between 0 and " + (V-1)); } /** * Adds the undirected