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

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

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:
 
  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. 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