This is a coding exerciseintended to helping me study for my exam please help show me how to complete it. Help find solution to the ToComplete items.

 package homework; import stdlib.*; import java.util.ArrayList; import java.util.LinkedList; import algs41.Graph; import algs41.GraphGenerator; /** * The GraphPP class represents an undirected graph of vertices * named 0 through V-1. * It uses an 'enhanced' adjacency list representation. (Q. what is the enhancement? ) * * It supports the following operations: * - addEdge add an edge to the graph, * - deleteEdge remove an edge from the Graph * - adj iterate over all of the neighbors adjacent to a vertex. * - addVertex add a vertex to the graph * - deleteVertex remove a vertex to the graph * - V return the number of vertices * - E return the number of edges * - hasEdge determine if an edge exists * * Parallel edges and self-loops are NOT permitted. */ /* * * GraphPP (Graph++ -an incrementally better graph implementation) * an adjacency list is Maked using an ArrayList of LinkedLists * compare to Author's array of Bags * * Several methods are provided as examples of how to work with an ArrayList of LinkedLists * see the video overview for more details * * Complete the 3 TOCompletes items * And determine the order of growth of the method in terms of V,E * place your answers in the space provided below. You must include a brief justification. * * You must not change the declaration of any method. * You may add your own utility instance methods if you want * * ------------------------------------------------------------------------------------------ * * Order of growth answers go here * Name: Order of growth Brief explanation * TOComplete1 E() * ToComplete2 adj() * TOComplete3 deleteVertex * ------------------------------------------------------------------------------------------ * * */ public class GraphPP { // Graph++ - incrementally better than the old Graph // V, E instance variables are not here! private ArrayList> aloll; //an adjacency list stored in an ArrayListOfLinkedLists /** * Make an empty graph with V vertices. */ @SuppressWarnings("unchecked") public GraphPP(int V) { if (V < 0) throw new Error("Number of vertices must be nonnegative"); aloll = new ArrayList(); for (int i=0; i < V; i++) { LinkedList aLinkedList = new LinkedList(); aloll.add(aLinkedList); } } /* V * return the number of vertices in the graph */ public int V() { return aloll.size(); } // the arrayList knows its size /** * Add the undirected edge v-w to graph. * @throws java.lang.IndexOutOfBoundsException unless both 0 <= v < V and 0 <= w < V * * enforces no self loops or parallel edges * verifies that v,w are valid vertices - throws an exception if not * * return true if edge was successfully added * return false otherwise */ public boolean addEdge(int v, int w) { if (v < 0 || v >= this.V()) throw new IndexOutOfBoundsException(); if (w < 0 || w >= this.V()) throw new IndexOutOfBoundsException(); if ( v == w ) return false; // ? if ( aloll.get(v).contains(w)) return false; // what is this 'trying' to complete? // add w to v's list and v to w's list LinkedList veesAdjList = aloll.get(v); // get a reference to v's list from the arrayList veesAdjList.add(w); // add w to v's list aloll.get(w).add(v); // one-line version of the above to add v to w's list return true; } /** * delete the undirected edge v-w from the graph * * verifies that v,w are valid vertices - throw an exception if not * * return true if edge was successfully deleted * return false otherwise */ public boolean deleteEdge(int v, int w) { if (v < 0 || v >= this.V()) throw new IndexOutOfBoundsException(); if (w < 0 || w >= this.V()) throw new IndexOutOfBoundsException(); boolean delw = aloll.get(v).remove( (Integer) w); // uses Object version of remove int indexOfV = aloll.get(w).indexOf(v); // get the 'index' of v within w's list int remValue = aloll.get(w).remove(indexOfV); // uses Index version of remove if ( delw && remValue == v ) { return true; } else return false; } /* * hasEdge * Determine if the graph has an edge between v,w * return true if edge exists * return false otherwise */ public boolean hasEdge(int v,int w) { if (aloll.get(v).contains(w) && aloll.get(w).contains(v) ) return true; return false; } /* add Vertex * * adds a vertex to the graph. * return: the numerical index of the newly added vertex * */ public int addVertex() { aloll.add(new LinkedList()); // extends the 'array' by one location // new location contains an empty list return aloll.size()-1; // new vertex is in the last space in the 'array' } /* * Return the number of edges in the graph. * * You MAY NOT use the size method of the LinkedList class * (Hint: LinkedList is Iterable, so iterate through each list) */ public int E() { // TOComplete1: fix this *** see the restrictions above! return -1; } /* * adj * * Return the list of neighbors of vertex v as an Iterable. * @throws java.lang.IndexOutOfBoundsException for an invalid vertex * * You MAY NOT return a reference to the actual LinkedList instance * Hint: Make some type of Iterable and populate it with the contents of * the corresponding list */ public Iterable adj(int v) { // TOomplete2 fix/implement this method if (v < 0 || v >= this.V()) throw new IndexOutOfBoundsException(); return null; // here is the alternate approach discussed in overview video // return aloll.get(v); this would return a reference to the actual list, which could then // allow the recipient to alter the graph :( } /* deleteVertex * * MUST: * remove vertex v if it exists * remove all edges involving vertex v * * compress the arrayList by moving the last vertex to the deleted vertex array location * NOTE: this means updating all the references to that vertex in the rest of the data structure * * Example: delete vertex 4 in a graph of size 10. (vertices are 0,1,...,9 ) * After deleting vertex 4 and all its edges, move vertex 9's list to * the now unused array location 4 * effectively replacing the old vertex 4 with that vertex. * any edge involving 9 should now refer to 4 * * Hint: first remove the old (9s), then add the (4) * * returns: * true if successful * false if v was invalid */ public boolean deleteVertex(int v) { //TOComplete3 implement this method return false; } /* * call some testing methods * * all tests require manual review of output * */ public static void main(String[] args) { // comment in/out while working on various ToCompletes constructorTest(); // just for reference //ETests(); //adjTests(); //deleteVertexTests(); } /* /* * Constructor / basic addEdge test * * Make a graph from file * print: file contents * print: actual graph data from adjacency lists * compare output manually * * provided just as a testing example */ public static void constructorTest() { String fileName; fileName = "data/tinyG.txt"; // fileName = "data/tinyCG.txt" StdOut.println( "Constructor test. graph data from file"); In in = new In(fileName); while (! in.isEmpty()) { StdOut.println( in.readLine()); } in = new In(fileName); GraphPP G = fromIn(in); // Make graph from data file StdOut.println( "actual graph info"); StdOut.println( G); //G.toGraphviz ("g.png"); } /* * E() tests * * Make graph info from file or using GraphGenerator * print actual graph info * call and print E() method * compare results manually */ public static void ETests() { String fileName; fileName = "data/tinyG.txt"; // fileName = "data/tinyCG.txt" In in = new In(fileName); GraphPP G = fromIn(in); // Make graph from data file //G = fromG( GraphGenerator.binaryTree(6) ); //G = fromG( GraphGenerator.wheel(6)); StdOut.println( "actual graph info"); StdOut.println( G); StdOut.println( " E() number of edges: " + G.E()); //G.toGraphviz ("g.png"); } /* * adj() tests * * Make graph info from file or using GraphGenerator * print actual graph info * print graph info using adj method * compare results manually */ public static void adjTests() { String fileName; fileName = "data/tinyG.txt"; // fileName = "data/tinyCG.txt" In in = new In(fileName); GraphPP G = fromIn(in); // Make graph from data file //G = fromG( GraphGenerator.binaryTree(6) ); //G = fromG( GraphGenerator.wheel(6)); StdOut.println(" adjTest results"); StdOut.println( "actual graph info"); StdOut.println( G); StdOut.println( "Graph using adj method"); for ( int v = 0; v < G.V(); v++) { StdOut.format(" %2d : ", v); for (int w : G.adj(v)) StdOut.format(" %d", w); StdOut.println(); } //G.toGraphviz ("g.png"); } /* * deleteVertexTests * * Make a graph * print actual graph data from adjacency lists * delete some vertices * print resulting graph * manually compare * * ( can also use graphViz images to compare ) */ public static void deleteVertexTests() { String fileName; fileName = "data/tinyG.txt"; // fileName = "data/tinyCG.txt" In in = new In(fileName); GraphPP G = fromIn(in); // Make graph from data file //G = fromG( GraphGenerator.binaryTree(6) ); //G = fromG( GraphGenerator.wheel(6)); StdOut.println( "Delete Vertex Test"); StdOut.println( "Graph Before"); StdOut.println( G); G.toGraphviz ("gBefore.png"); // delete some vertices G.deleteVertex(4); StdOut.println( "Graph After"); StdOut.println( G); G.toGraphviz ("gAfter.png"); } /* ********************************************************************** * utility routines; look but don't alter */ /** * Return a string representation of the graph. */ public String toString() { StringBuilder s = new StringBuilder(); String NEWLINE = System.getProperty("line.separator"); s.append(this.V() + " vertices, " + E() + " edges " + NEWLINE); for (int v = 0; v < aloll.size(); v++) { s.append(v + ": "); for ( int w : aloll.get(v)) { s.append(w + " "); } s.append(NEWLINE); } return s.toString(); } /** * Save a graphviz representation of the graph. * See graphviz.org. */ public void toGraphviz(String filename) { GraphvizBuilder gb = new GraphvizBuilder (); for (int v = 0; v < aloll.size(); v++) { gb.addNode (v); boolean showSelfLoop = false; for (int w : aloll.get(v)) { if (v < w) // only once each edge gb.addEdge (v, w); if (v == w) { showSelfLoop = !showSelfLoop; if (showSelfLoop) gb.addEdge (v, w); } } } gb.toFileUndirected (filename); } /* fromIn * * Make an GraphPP from an input file * * requires addEdge for correct operation */ public static GraphPP fromIn (In in) { GraphPP G = new GraphPP (in.readInt()); int E = in.readInt(); for (int i = 0; i < E; i++) { int v = in.readInt(); int w = in.readInt(); G.addEdge(v, w); } return G; } /* fromG * * Make an GraphPP from the textbook Graph class * */ public static GraphPP fromG (Graph AG) { GraphPP G = new GraphPP (AG.V()); for ( int v=0; v < AG.V(); v++) for ( int w : AG.adj(v)) if ( v < w ) G.addEdge(v, w); return G; } } 

imports

// Exercise 4.1.3 (Solution published at http://algs4.cs.princeton.edu/) package algs41; import stdlib.*; import algs13.Bag; /** * The Graph class represents an undirected graph of vertices * named 0 through V-1. * It supports the following operations: add an edge to the graph, * iterate over all of the neighbors adjacent to a vertex. * Parallel edges and self-loops are permitted. * 
 * For additional documentation, see Section 5.1 of * Algorithms, 4th Edition by Robert Sedgewick and Kevin Wayne. */ public class Graph { private final int V; private int E; private final Bag[] adj; /** * Make an empty graph with V vertices. */ @SuppressWarnings("unchecked") public Graph(int V) { if (V < 0) throw new Error("Number of vertices must be nonnegative"); this.V = V; this.E = 0; this.adj = new Bag[V]; for (int v = 0; v < V; v++) { adj[v] = new Bag<>(); } } /** * Return the number of vertices in the graph. */ public int V() { return V; } /** * Return the number of edges in the graph. */ public int E() { return E; } /** * Add the undirected edge v-w to graph. * @throws java.lang.IndexOutOfBoundsException unless both 0 <= v < V and 0 <= w < V */ public void addEdge(int v, int w) { if (v < 0 || v >= V) throw new IndexOutOfBoundsException(); if (w < 0 || w >= V) throw new IndexOutOfBoundsException(); E++; adj[v].add(w); adj[w].add(v); } /** * Return the list of neighbors of vertex v as in Iterable. * @throws java.lang.IndexOutOfBoundsException unless 0 <= v < V */ public Iterable adj(int v) { if (v < 0 || v >= V) throw new IndexOutOfBoundsException(); return adj[v]; } /** * Returns the degree of vertex {@code v}. * * @param v the vertex * @return the degree of vertex {@code v} * @throws IllegalArgumentException unless {@code 0 <= v < V} */ public int degree(int v) { if (v < 0 || v >= V) throw new IndexOutOfBoundsException(); return adj[v].size(); } /** * Return a string representation of the graph. */ public String toString() { StringBuilder s = new StringBuilder(); String NEWLINE = System.getProperty("line.separator"); s.append(V + " vertices, " + E + " edges " + NEWLINE); for (int v = 0; v < V; v++) { s.append(v + ": "); for (int w : adj[v]) { s.append(w + " "); } s.append(NEWLINE); } return s.toString(); } /** * Save a graphviz representation of the graph. * See graphviz.org. */ public void toGraphviz(String filename) { GraphvizBuilder gb = new GraphvizBuilder (); for (int v = 0; v < V; v++) { gb.addNode (v); boolean showSelfLoop = false; for (int w : adj[v]) { if (v < w) // only once each edge gb.addEdge (v, w); if (v == w) { showSelfLoop = !showSelfLoop; if (showSelfLoop) gb.addEdge (v, w); } } } gb.toFileUndirected (filename); } /** * Test client. */ public static void main(String[] args) { //args = new String [] { "data/tinyCG.txt" }; args = new String [] { "data/tinyG.txt" }; //args = new String [] { "20", "40" }; Graph G; if (args.length == 1) { In in = new In(args[0]); G = GraphGenerator.fromIn (in); } else { int V = Integer.parseInt (args[0]); int E = Integer.parseInt (args[1]); G = GraphGenerator.simple(V, E); } StdOut.println(G); G.toGraphviz ("g.png"); } } 

package algs41; import java.util.Arrays; import algs13.Stack; import algs24.MinPQ; import stdlib.*; public class GraphGenerator { /** * Make a graph from input stream. */ public static Graph fromIn (In in) { Graph G = new Graph (in.readInt()); int E = in.readInt(); for (int i = 0; i < E; i++) { int v = in.readInt(); int w = in.readInt(); G.addEdge(v, w); } return G; } public static Graph copy (Graph G) { Graph R = new Graph (G.V()); for (int v = 0; v < G.V(); v++) { // reverse so that adjacency list is in same order as original Stack reverse = new Stack(); for (int w : G.adj(v)) { reverse.push(w); } for (int w : reverse) { R.addEdge (v, w); } } return R; } public static Graph complete (int V) { return simple (V, V * (V - 1) / 2); } public static Graph simple (int V, int E) { if (V < 0 || E < 0) throw new IllegalArgumentException (); if (E > V * (V - 1) / 2) throw new IllegalArgumentException ("Number of edges must be less than V*(V-1)/2"); Graph G = new Graph (V); newEdge: while (E > 0) { int v = StdRandom.uniform (V); int w = StdRandom.uniform (V); if (v == w) continue; for (int w2 : G.adj (v)) if (w == w2) continue newEdge; G.addEdge (v, w); E--; } return G; } public static Graph simpleConnected (int V, int E) { if (V < 0 || E < 0) throw new IllegalArgumentException (); if (E > V * (V - 1) / 2) throw new IllegalArgumentException ("Number of edges must be less than V*(V-1)/2"); Graph G = spanningTree (V); newEdge: while (G.E () < E) { int v = StdRandom.uniform (V); int w = StdRandom.uniform (V); if (v == w) continue; for (int w2 : G.adj (v)) if (w == w2) continue newEdge; G.addEdge (v, w); E--; } return G; } public static Graph connected (int V, int E) { if (V < 0 || E < 0) throw new IllegalArgumentException (); Graph G = spanningTree (V); while (G.E () < E) { int v = StdRandom.uniform (V); int w = StdRandom.uniform (V); G.addEdge (v, w); } return G; } public static Graph random (int V, int E) { if (V < 0 || E < 0) throw new IllegalArgumentException (); Graph G = new Graph (V); while (G.E () < E) { int v = StdRandom.uniform (V); int w = StdRandom.uniform (V); G.addEdge (v, w); } return G; } public static Graph spanningTree (int V) { if (V < 1) throw new IllegalArgumentException (); int[] vertices = new int[V]; for (int i = 0; i < V; i++) vertices[i] = i; StdRandom.shuffle (vertices); Graph G = new Graph (V); for (int i = 1; i < V; i++) { int v = vertices[StdRandom.uniform (i)]; int w = vertices[i]; G.addEdge (v, w); } return G; } public static Graph connected(int V, int E, int c) { if (c >= V || c <= 0) throw new IllegalArgumentException("Number of components must be between 1 and V"); if (E <= (V-c)) throw new IllegalArgumentException("Number of edges must be at least (V-c)"); if (E > V * (V - 1) / 2) throw new IllegalArgumentException("Too many edges"); int[] label = new int[V]; for (int v = 0; v < V; v++) { label[v] = StdRandom.uniform(c); } // The following hack ensures that each color appears at least once { Arrays.sort (label); label[0] = 0; for (int v = 1; v < V; v++) { if (label[v]-label[v-1] > 1 || V-v == c-label[v-1]-1) label[v] = label[v-1]+1; } StdRandom.shuffle (label); } // make all vertices with label c a connected component Graph G = new Graph(V); for (int i = 0; i < c; i++) { // how many vertices in component c int count = 0; for (int v = 0; v < V; v++) { if (label[v] == i) count++; } int[] vertices = new int[count]; { int j = 0; for (int v = 0; v < V; v++) if (label[v] == i) vertices[j++] = v; } StdRandom.shuffle(vertices); for (int j = 1; j < count; j++) { int v = vertices[StdRandom.uniform (j)]; int w = vertices[j]; G.addEdge (v, w); } } while (G.E() < E) { int v = StdRandom.uniform(V); int w = StdRandom.uniform(V); if (v != w && label[v] == label[w]) { G.addEdge(v, w); } } return G; } /** * Returns a random simple bipartite graph on {@code V1} and {@code V2} vertices, * containing each possible edge with probability {@code p}. * @param V1 the number of vertices in one partition * @param V2 the number of vertices in the other partition * @param p the probability that the graph contains an edge with one endpoint in either side * @return a random simple bipartite graph on {@code V1} and {@code V2} vertices, * containing each possible edge with probability {@code p} * @throws IllegalArgumentException if probability is not between 0 and 1 */ public static Graph bipartite(int V1, int V2, double p) { if (p < 0.0 || p > 1.0) throw new IllegalArgumentException("Probability must be between 0 and 1"); int[] vertices = new int[V1 + V2]; for (int i = 0; i < V1 + V2; i++) vertices[i] = i; StdRandom.shuffle(vertices); Graph G = new Graph(V1 + V2); for (int i = 0; i < V1; i++) for (int j = 0; j < V2; j++) if (StdRandom.bernoulli(p)) G.addEdge(vertices[i], vertices[V1+j]); return G; } /** * Returns a path graph on {@code V} vertices. * @param V the number of vertices in the path * @return a path graph on {@code V} vertices */ public static Graph path(int V) { Graph G = new Graph(V); int[] vertices = new int[V]; for (int i = 0; i < V; i++) vertices[i] = i; StdRandom.shuffle(vertices); for (int i = 0; i < V-1; i++) { G.addEdge(vertices[i], vertices[i+1]); } return G; } /** * Returns a complete binary tree graph on {@code V} vertices. * @param V the number of vertices in the binary tree * @return a complete binary tree graph on {@code V} vertices */ public static Graph binaryTree(int V) { Graph G = new Graph(V); int[] vertices = new int[V]; for (int i = 0; i < V; i++) vertices[i] = i; StdRandom.shuffle(vertices); for (int i = 1; i < V; i++) { G.addEdge(vertices[i], vertices[(i-1)/2]); } return G; } /** * Returns a cycle graph on {@code V} vertices. * @param V the number of vertices in the cycle * @return a cycle graph on {@code V} vertices */ public static Graph cycle(int V) { Graph G = new Graph(V); int[] vertices = new int[V]; for (int i = 0; i < V; i++) vertices[i] = i; StdRandom.shuffle(vertices); for (int i = 0; i < V-1; i++) { G.addEdge(vertices[i], vertices[i+1]); } G.addEdge(vertices[V-1], vertices[0]); return G; } /** * Returns an Eulerian cycle graph on {@code V} vertices. * * @param V the number of vertices in the cycle * @param E the number of edges in the cycle * @return a graph that is an Eulerian cycle on {@code V} vertices * and {@code E} edges * @throws IllegalArgumentException if either {@code V <= 0} or {@code E <= 0} */ public static Graph eulerianCycle(int V, int E) { if (E <= 0) throw new IllegalArgumentException("An Eulerian cycle must have at least one edge"); if (V <= 0) throw new IllegalArgumentException("An Eulerian cycle must have at least one vertex"); Graph G = new Graph(V); int[] vertices = new int[E]; for (int i = 0; i < E; i++) vertices[i] = StdRandom.uniform(V); for (int i = 0; i < E-1; i++) { G.addEdge(vertices[i], vertices[i+1]); } G.addEdge(vertices[E-1], vertices[0]); return G; } /** * Returns an Eulerian path graph on {@code V} vertices. * * @param V the number of vertices in the path * @param E the number of edges in the path * @return a graph that is an Eulerian path on {@code V} vertices * and {@code E} edges * @throws IllegalArgumentException if either {@code V <= 0} or {@code E < 0} */ public static Graph eulerianPath(int V, int E) { if (E < 0) throw new IllegalArgumentException("negative number of edges"); if (V <= 0) throw new IllegalArgumentException("An Eulerian path must have at least one vertex"); Graph G = new Graph(V); int[] vertices = new int[E+1]; for (int i = 0; i < E+1; i++) vertices[i] = StdRandom.uniform(V); for (int i = 0; i < E; i++) { G.addEdge(vertices[i], vertices[i+1]); } return G; } /** * Returns a wheel graph on {@code V} vertices. * @param V the number of vertices in the wheel * @return a wheel graph on {@code V} vertices: a single vertex connected to * every vertex in a cycle on {@code V-1} vertices */ public static Graph wheel(int V) { if (V <= 1) throw new IllegalArgumentException("Number of vertices must be at least 2"); Graph G = new Graph(V); int[] vertices = new int[V]; for (int i = 0; i < V; i++) vertices[i] = i; StdRandom.shuffle(vertices); // simple cycle on V-1 vertices for (int i = 1; i < V-1; i++) { G.addEdge(vertices[i], vertices[i+1]); } G.addEdge(vertices[V-1], vertices[1]); // connect vertices[0] to every vertex on cycle for (int i = 1; i < V; i++) { G.addEdge(vertices[0], vertices[i]); } return G; } /** * Returns a star graph on {@code V} vertices. * @param V the number of vertices in the star * @return a star graph on {@code V} vertices: a single vertex connected to * every other vertex */ public static Graph star(int V) { if (V <= 0) throw new IllegalArgumentException("Number of vertices must be at least 1"); Graph G = new Graph(V); int[] vertices = new int[V]; for (int i = 0; i < V; i++) vertices[i] = i; StdRandom.shuffle(vertices); // connect vertices[0] to every other vertex for (int i = 1; i < V; i++) { G.addEdge(vertices[0], vertices[i]); } return G; } /** * Returns a uniformly random {@code k}-regular graph on {@code V} vertices * (not necessarily simple). The graph is simple with probability only about e^(-k^2/4), * which is tiny when k = 14. * * @param V the number of vertices in the graph * @param k degree of each vertex * @return a uniformly random {@code k}-regular graph on {@code V} vertices. */ public static Graph regular(int V, int k) { if (V*k % 2 != 0) throw new IllegalArgumentException("Number of vertices * k must be even"); Graph G = new Graph(V); // Make k copies of each vertex int[] vertices = new int[V*k]; for (int v = 0; v < V; v++) { for (int j = 0; j < k; j++) { vertices[v + V*j] = v; } } // pick a random perfect matching StdRandom.shuffle(vertices); for (int i = 0; i < V*k/2; i++) { G.addEdge(vertices[2*i], vertices[2*i + 1]); } return G; } // http://www.proofwiki.org/wiki/Labeled_Tree_from_Prfer_Sequence // http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.36.6484&rep=rep1&type=pdf /** * Returns a uniformly random tree on {@code V} vertices. * This algorithm uses a Prufer sequence and takes time proportional to V log V. * @param V the number of vertices in the tree * @return a uniformly random tree on {@code V} vertices */ public static Graph tree(int V) { Graph G = new Graph(V); // special case if (V == 1) return G; // Cayley's theorem: there are V^(V-2) labeled trees on V vertices // Prufer sequence: sequence of V-2 values between 0 and V-1 // Prufer's proof of Cayley's theorem: Prufer sequences are in 1-1 // with labeled trees on V vertices int[] prufer = new int[V-2]; for (int i = 0; i < V-2; i++) prufer[i] = StdRandom.uniform(V); // degree of vertex v = 1 + number of times it appers in Prufer sequence int[] degree = new int[V]; for (int v = 0; v < V; v++) degree[v] = 1; for (int i = 0; i < V-2; i++) degree[prufer[i]]++; // pq contains all vertices of degree 1 MinPQ pq = new MinPQ(); for (int v = 0; v < V; v++) if (degree[v] == 1) pq.insert(v); // repeatedly delMin() degree 1 vertex that has the minimum index for (int i = 0; i < V-2; i++) { int v = pq.delMin(); G.addEdge(v, prufer[i]); degree[v]--; degree[prufer[i]]--; if (degree[prufer[i]] == 1) pq.insert(prufer[i]); } G.addEdge(pq.delMin(), pq.delMin()); return G; } public static void print (Graph G, String filename) { if (G == null) return; System.out.println (filename); System.out.println (G); System.out.println (); G.toGraphviz (filename + ".png"); } public static void main (String[] args) { //StdRandom.setSeed (10); args = new String[] { "6", "10", "3" }; int V = Integer.parseInt (args[0]); int E = Integer.parseInt (args[1]); int c = Integer.parseInt (args[2]); for (int i= 5; i>0; i--) { print (GraphGenerator.random (V, E), "random-" + V + "-" + E); print (GraphGenerator.random (V, E), "random-" + V + "-" + E); print (GraphGenerator.simple (V, E), "simple-" + V + "-" + E); print (GraphGenerator.complete (V), "complete-" + V); print (GraphGenerator.spanningTree (V), "spanningTree-" + V); print (GraphGenerator.simpleConnected (V, E), "simpleConnected-" + V + "-" + E); print (GraphGenerator.connected (V, E), "connected-" + V + "-" + E); print (GraphGenerator.path (V), "path-" + V); print (GraphGenerator.binaryTree (V), "binaryTree-" + V); print (GraphGenerator.cycle (V), "cycle-" + V); if (E <= (V - c)) E = (V - c) + 1; print (GraphGenerator.connected (V, E, c), "connected-" + V + "-" + E + "-" + c); print (GraphGenerator.eulerianCycle (V, E), "eulerian-" + V + "-" + E); } } }

package algs13; import stdlib.*; import java.util.ConcurrentModificationException; import java.util.Iterator; import java.util.ListIterator; import java.util.NoSuchElementException; /* *********************************************************************** * Compilation: javac LinkedList.java * Execution: java LinkedList * * A list implemented with a doubly linked list. The elements are stored * (and iterated over) in the same order that they are inserted. * * % java List * This * is * a * test. * * This * is * a * test. * *************************************************************************/ public class LinkedList implements Iterable { private int N; // number of elements on list private final Node pre; // sentinel before first item private final Node post; // sentinel after last item private long opcount; public LinkedList() { pre = new Node<>(); post = new Node<>(); pre.next = post; post.prev = pre; } // linked list node helper data type private static class Node { public Node() { } public T item; public Node next; public Node prev; } public boolean isEmpty() { return N == 0; } public int size() { return N; } // add the item to the end of the list public void add(T item) { Node last = post.prev; Node x = new Node<>(); x.item = item; x.next = post; x.prev = last; post.prev = x; last.next = x; N++; opcount++; } public ListIterator iterator() { return new LinkedListIterator(); } // assumes no calls to add() during iteration private class LinkedListIterator implements ListIterator { private Node current = pre.next; // the node that is returned by next() private Node lastAccessed = null; // the last node to be returned by prev() or next() // reset to null upon intervening remove() or add() private int index = 0; private long oc = opcount; private void ocCheck() { if (opcount != oc) throw new ConcurrentModificationException (); } private void ocInc() { ocCheck(); opcount++; oc++; } public boolean hasNext() { ocCheck(); return index < N; } public boolean hasPrevious() { ocCheck(); return index > 0; } public int previousIndex() { ocCheck(); return index - 1; } public int nextIndex() { ocCheck(); return index; } public T next() { ocCheck(); if (!hasNext()) throw new NoSuchElementException(); lastAccessed = current; T item = current.item; current = current.next; index++; return item; } public T previous() { ocCheck(); if (!hasPrevious()) throw new NoSuchElementException(); current = current.prev; lastAccessed = current; T item = current.item; index--; return item; } // replace the item of the element that was last accessed by next() or previous() // condition: no calls to remove() or add() after last call to next() or previous() public void set(T item) { ocInc(); if (lastAccessed == null) throw new Error(); lastAccessed.item = item; } // remove the element that was last accessed by next() or previous() // condition: no calls to remove() or add() after last call to next() or previous() public void remove() { ocInc(); if (lastAccessed == null) throw new Error(); Node lastPrev = lastAccessed.prev; Node lastNext = lastAccessed.next; lastPrev.next = lastNext; lastNext.prev = lastPrev; N--; if (current == lastAccessed) current = lastNext; else index--; lastAccessed = null; } // add element to list public void add(T item) { ocInc(); Node first = current.prev; Node middle = new Node<>(); Node last = current; middle.item = item; first. next = middle; middle.next = last; last. prev = middle; middle.prev = first; N++; index++; lastAccessed = null; } } public String toString () { StringBuilder sb = new StringBuilder (); Iterator it = this.iterator (); if (it.hasNext ()) sb.append (it.next ()); while (it.hasNext ()) { sb.append (" "); sb.append (it.next ()); } return sb.toString (); } public static  void printForward(String s, LinkedList list, ListIterator iterator) { StdOut.println(); StdOut.println(s); StdOut.println(list); while (iterator.hasNext()) StdOut.format ("[%d,%d] ", iterator.nextIndex (), iterator.next ()); while (iterator.hasPrevious()) StdOut.format ("[%d,%d] ", iterator.previousIndex (), iterator.previous()); StdOut.println (); } public static  void printBackward(String s, LinkedList list, ListIterator iterator) { StdOut.println(); StdOut.println(s); StdOut.println(list); while (iterator.hasPrevious()) StdOut.format ("[%d,%d] ", iterator.previousIndex (), iterator.previous()); while (iterator.hasNext()) StdOut.format ("[%d,%d] ", iterator.nextIndex (), iterator.next ()); StdOut.println (); } // a test client public static void main(String[] args) { LinkedList list = new LinkedList<>(); list.add(93); list.add(48); list.add(94); list.add(4); list.add(48); list.add(94); ListIterator iterator = list.iterator(); printForward ("original", list, iterator); // set forwards while (iterator.hasNext()) { int x = iterator.next(); iterator.set(x + 1); } printBackward ("after set forward", list, iterator); // set backwards while (iterator.hasPrevious()) { int x = iterator.previous(); iterator.set(3 * x); } printForward ("after set backward", list, iterator); // remove forwards while (iterator.hasNext()) { int x = iterator.next(); if (x % 2 == 0) iterator.remove(); } printBackward ("after remove forward", list, iterator); // remove backwards while (iterator.hasPrevious()) { int x = iterator.previous(); if (x % 5 == 0) iterator.remove(); } printForward ("after remove backward", list, iterator); // add forwards while (iterator.hasNext()) { int x = iterator.next(); iterator.add(x + 10); } printBackward ("after add forward", list, iterator); // add backwards while (iterator.hasPrevious()) { int x = iterator.previous(); iterator.add(x - 1); iterator.previous(); } printForward ("after add backward", list, iterator); } }