Please code in Java and add comments for my understanding. A Start-up code + Pseudo code is given to implement DFS and BFS. Thanks!

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

Functions to Work on: --------------------------------------------------------------------------------------------

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

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

STARTER CODE BELOW: ---------------------------------------------------------------------------------------------------------------------

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  DFS(Node s) { // implement this } // DFS() //------------------------------------------------ public List BFS(Node s) { // implement this } // BFS() } // 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

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