Depth First Search

The depth first search algorithm works in a way that is reasonable given its title. Basically, it works in that you start at a node, go to one of its neighbors, go one of that nodes neighbors, until you reach a node with no neighbors (that you haven't visited). This means that there are technically multiple possible DFSs for the above graph starting at node 5, 2 or 3. To display my point two possible DFSs starting at node 5 are {5, 3, 2, 4, 6} and {5, 2, 3, 4, 6}.

Sometimes, you will have weighted edges which can be used to determine which neighbor node is chosen, but not in this lab. In your code, if you write it to the specifications, there will be no ambiguity because you will simply go off of the order in which you added nodes and edges. Note: when you print the nodes out in DFS order, you should print a space between each node. (A trailing space after the last node is fine.)

import java.io.IOException; import java.io.PrintWriter; import java.util.ArrayList;

public class Graph> extends GraphAbstract { public Graph() { nodes = new ArrayList(); }

/* addEdge * Params: data1 & data2, both data items to be added and connected * If the either of the data items are not in the nodes ArrayList, * add them as new nodes. Otherwise, find the nodes in the ArrayList so * you can make them point to each other. Implement so there are no duplicates * added to either of the nodes neighbors ArrayList. * TODO: implement this method. * */ @Override public void addEdge(E data1, E data2) { //YOUR CODE HERE }

/* depthFirst * Param: startNode, the node to start the traversal at * * First, find the startNode based off of startItem (hint: indexOf()) * I recommend having an ArrayList of GraphNodes called visisted to keep * track of the nodes you've visited. * * Prints all of the nodes in the graph in depth first order (with a space between nodes) * TODO: implement this method. * */ @Override public void depthFirst(E startItem) { //YOUR CODE HERE }

// Recursive helper method for depthFirst private void depthFirst(GraphNode curr, ArrayList visited) { //YOUR CODE HERE }

}

import java.util.ArrayList;

public abstract class GraphAbstract> {

/* GraphNode subclass * A node in the graph which has an ArrayList of all it's neighbors * i.e. the nodes it points to. */ public class GraphNode { public E data; public ArrayList neighbors;

public GraphNode(E data) { this.data = data; neighbors = new ArrayList<>(); }

public boolean equals(Object o) { if (o instanceof GraphAbstract.GraphNode) { GraphAbstract.GraphNode otherNode = (GraphAbstract.GraphNode) o; return this.data.equals(otherNode.data); } return false; } public int hashCode() { return super.hashCode(); } }

// stores all of the nodes in the graph public ArrayList nodes;

public abstract void addEdge(E data1, E data2);

// print graph in depth first order beginning at startNode public abstract void depthFirst(E startNode); }

public class GraphTest { public static void main(String[] args) { Graph graph = new Graph<>();

graph.addEdge(5, 3); graph.addEdge(5, 2); graph.addEdge(2, 3); graph.addEdge(2, 4); graph.addEdge(4, 6); System.out.println("Expected: 5 3 2 4 6 "); System.out.print("Your result: "); graph.depthFirst(5); System.out.println(); System.out.println("Expected: 3 5 2 4 6 "); System.out.print("Your result: "); graph.depthFirst(3);

// As always, feel free to write more tests to help gain a better understanding. } }