My code + Pseudo code is given; please verify the accuracy of BFS and DFS functions in Graph.java. The top half is just background instructions for context; please code ( in java) the section at the bottom labeled "Graduate Students". Provide comments for my understanding and insert screenshots of output. Thanks!

---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

Background Instructions Below (Up until section number 2)

DFS Pseudo code: --------------------------------------------------------------------------------------------

BFS Pseudo code: --------------------------------------------------------------------------------------------

CODE Files : ---------------------------------------------------------------------------------------------------------------------

1) Graph.java *********************************************************************

import java.util.List; import java.util.ArrayList; import java.util.Stack; import java.util.Queue; import java.util.LinkedList; public class Graph { List nodes; //------------------------------------------------ public Graph() { nodes = new ArrayList(); } //------------------------------------------------ public void addNode(Node node) { for (Node n: this.nodes) { if (n == node) { System.out.println("ERROR: graph already has a node " + n.name); assert false; } } this.nodes.add(node); } //------------------------------------------------ public void addEdge(Node n1, Node n2) { // outgoing edge int idx1 = this.nodes.indexOf(n1); if (idx1  
public List DFS(Node s) { // DFS function to verify ******************************************************************************************************
 
 Stack stack = new Stack();
 
 List visited = new ArrayList();
 
 boolean[] explored = new boolean[this.nodes.size() + 1];
 
 stack.push(s);
 
 while (!stack.empty()) {
 
 Node u = stack.pop();
 
 if (!explored[u.name]) {
 
 explored[u.name] = true;
 
 visited.add(u);
 
 for (Node v : u.adjlist) {
 
 stack.push(v);
 
 }
 
 }
 
 }
 
 return visited;
 
 }
 
 //------------------------------------------------
 
public List BFS(Node s) { // BFS function to verify **********************************************************************************
 
 Queue queue = new LinkedList();
 
 List visited = new ArrayList();
 
 boolean[] discovered = new boolean[this.nodes.size() + 1];
 
 queue.offer(s);
 
 discovered[s.name] = true;
 
 while (!queue.isEmpty()) {
 
 Node u = queue.poll();
 
 visited.add(u);
 
 for (Node v : u.adjlist) {
 
 if (!discovered[v.name]) {
 
 queue.offer(v);
 
 discovered[v.name] = true;
 
 }
 
 }
 
 }
 
 return visited;
 
 }
 
} // class Graph 
 
2) Main.java ************************************************************************
 
import java.util.List; public class Main { public static void main(String args[]) { testOne(); } //-------------------------------------------- // this is the graph in Fig. 3.2 public static void testOne() { Node n1 = new Node(1); Node n2 = new Node(2); Node n3 = new Node(3); Node n4 = new Node(4); Node n5 = new Node(5); Node n6 = new Node(6); Node n7 = new Node(7); Node n8 = new Node(8); Node n9 = new Node(9); Node n10 = new Node(10); Node n11 = new Node(11); Node n12 = new Node(12); Node n13 = new Node(13); Graph G = new Graph(); G.addNode(n1); G.addNode(n2); G.addNode(n3); G.addNode(n4); G.addNode(n5); G.addNode(n6); G.addNode(n7); G.addNode(n8); G.addNode(n9); G.addNode(n10); G.addNode(n11); G.addNode(n12); G.addNode(n13); G.addEdge(n1, n2); G.addEdge(n1, n3); G.addEdge(n2, n4); G.addEdge(n2, n5); G.addEdge(n3, n7); G.addEdge(n3, n8); G.addEdge(n4, n5); G.addEdge(n5, n6); G.addEdge(n7, n8); G.addEdge(n9, n10); G.addEdge(n11, n12); G.addEdge(n12, n13); System.out.println("--- DFS ---"); List cc = G.DFS(n1); System.out.print("["); for (Node n: cc) System.out.print(" " + n); System.out.println("]"); System.out.println("--- BFS ---"); cc = G.BFS(n1); System.out.print("["); for (Node n: cc) System.out.print(" " + n); System.out.println("]"); } // testOne() } // class Main 3) Node.java ***********************************************************************
 
 
 
import java.util.List; import java.util.ArrayList; public class Node { List adjlist; int name; //-------------------------------------------------- public Node(int name) { this.name = name; this.adjlist = new ArrayList(); } //-------------------------------------------------- public void addEdge(Node otherNode) { // make sure that this edge doesn't already exist for (Node n: this.adjlist) { if (n == otherNode) { System.out.println("ERROR: there is already an edge from " + this.name + " to " + otherNode.name); return; } } for (Node n: otherNode.adjlist) { if (n == this) { System.out.println("ERROR: there is already an edge from " + this.name + " to " + otherNode.name); return; } } // add edge from this to edge.tail this.adjlist.add(otherNode); // and vice versa otherNode.adjlist.add(this); } //-------------------------------------------------- @Override public boolean equals(Object o) { if (o == this) return true; if ( ! (o instanceof Node) ) return false; Node otherNode = (Node) o; if (otherNode.name == this.name) return true; return false; } //-------------------------------------------------- @Override public String toString() { String s = "" + this.name; return s; } } // class Node
 
-----------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
 
Please Code up this part:
 
  The graph will be represented as an adjacency list: each node will have a List of nodes, showing the nodes to which an edge exists. And the graph itself then consists of a List of nodes. Each node will have a "name", which will be an integer in the range 1,2,,n, where n is the number of nodes in the graph. This is slightly awkward in terms of arrays in Java, since Java arrays are zero-indexed. For example: suppose I want to keep an array boolean [] visited to show whether or not a node has been visited during graph traversal. In order to use the node's name as an index, I need to allocate the array to be of size n+1. Then, to check whether node s has been visited, I look at visited [s.name]. Once you start doing this, it will become natural for other CS224 programming assignments this semester. Do not make any changes to Node.java. Also, since these are undirected graphs, we model an edge from node s tol node t by putting t in the adjacency list for s and putting s in the adjacency list for t. However, specify an edge only once: Graph g= new Graph() Node n1 = new Node (1) Node n 2= new Node (2) g. addNode (n1) ; g. addNode (n2) ; g. addEdge (n1, n2) ; You'll see this in the test cases. Implement these two functions on Graph: public List DFS (Node s) ; public List BFS (Node s); function DFS (s) : initialize S to be a stack with one element s initialize each element of explored [] to be false while S is not empty \{ take a node u from S if explored [u]== false \{ set explored [u]= true for each edge (u, v) incident to u \{ add v to the stack S \} \} return list of explored nodes Define your stack this way: Stack  stack = new Stack  () Your function should return a list of all of the nodes that are in the same connected component as the node at which you start the traversal. function BFS(S): initialize each element of discovered [] to be false initialize Q to be a queue with one element s set discovered [s]= true while Q is not empty remove the next node u from Q for each edge (u, v ) incident to u \{ if discovered [v]== false set discovered [v]= true add v to Q \} \} return list of discovered nodes Define your queue this way: Queue  queue = new LinkedList (); Your function should return a list of all of the nodes that are in the same connected component as the node at which you start the traversal. 2 Testing and Development I've also given you a Main class that can use. Main has two test cases on which you can test your traversal code. Do not implement additional functions-just fill in the stubs for the two functions in Graph. Graduate students, and undergraduates for a bit of extra credit: we can model the "richness" of the connection between two nodes in a network (for example, in Linkedin) by counting the total number of shortest paths between them. We can easily compute this as a side-effect of a breadth-first traversal: - the number of shortest paths from node s to node s is one - if node v is in layer j of the BFS tree rooted at s, then the number of shortest paths from s to v is the sum of the number of shortest paths from s to each node t in layer j1 for which there is an edge (t,v) Write this function: public int [] numShortestPaths(Node s); It should return an array with the number of shortest paths from s to each node in the graph. Here's an example graph you can use as a testcase: Compute the number of shortest paths from node 1 to each node. Submit your files for the grad portion in MainGrad.java, NodeGrad.java, and GraphGrad.java