import java.util.*;

/**
* Your implementation of various different graph algorithms.
*
*/
public class GraphAlgorithms {

/**
* Performs a breadth first search (bfs) on the input graph, starting at
* {@code start} which represents the starting vertex.
*
* When exploring a vertex, make sure to explore in the order that the
* adjacency list returns the neighbors to you. Failure to do so may cause
* you to lose points.
*
* You may import/use {@code java.util.Set}, {@code java.util.List},
* {@code java.util.Queue}, and any classes that implement the
* aforementioned interfaces, as long as it is efficient.
*
* The only instance of {@code java.util.Map} that you may use is the
* adjacency list from {@code graph}. DO NOT create new instances of Map
* for BFS (storing the adjacency list in a variable is fine).
*
* DO NOT modify the structure of the graph. The graph should be unmodified
* after this method terminates.
*
* @throws IllegalArgumentException if any input
* is null, or if {@code start} doesn't exist in the graph
* @param <T> the generic typing of the data
* @param start the vertex to begin the bfs on
* @param graph the graph to search through
* @return list of vertices in visited order
*/
public static <T> List<Vertex<T>> bfs(Vertex<T> start, Graph<T> graph) {

   if(start == null || graph == null){
         throw new IllegalArgumentException("Invalid or null parameters");
   }

   if(!graph.getAdjList().containsKey(start)){
         throw new IllegalArgumentException("Invalid parameters");
   }

   Map<Vertex<T>, List<VertexDistance<T>>> adjList = graph.getAdjList();

   LinkedList<Vertex<T>> queue = new LinkedList<>();

   List<Vertex<T>> visited = new ArrayList<>();

   visited.add(start);
   queue.add(start);

   while (queue.size() != 0){
         start = queue.poll();
         List<VertexDistance<T>> vertexDistances = adjList.get(start);
         for (VertexDistance<T> vertex: vertexDistances){
               if(!visited(visited, vertex.getVertex())){
                     visited.add(vertex.getVertex());
                     queue.add(vertex.getVertex());
               }
         }
   }

   return visited;
}

/**
* Helper method to check if the given vertex
* is present in the list of all vertices.
* @param allVertices the list of vertices.
* @param search the vertex to be searched for.
* @param <T> the type of data it holds.
* @return the boolean value true if vertex
* is found, false, otherwise.
*/
private static <T> boolean visited(List<Vertex<T>> allVertices, Vertex<T> search){

   boolean found = false;
   for(Vertex<T> v: allVertices){
         if(v.equals(search)){
            found = true;
            break;
         }
   }

   return found;
}

/**
* Performs a depth first search (dfs) on the input graph, starting at
* {@code start} which represents the starting vertex.
*
* When exploring a vertex, make sure to explore in the order that the
* adjacency list returns the neighbors to you. Failure to do so may cause
* you to lose points.
*
* *NOTE* You MUST implement this method recursively, or else you will lose
* most if not all points for this method.
*
* You may import/use {@code java.util.Set}, {@code java.util.List}, and
* any classes that implement the aforementioned interfaces, as long as it
* is efficient.
*
* The only instance of {@code java.util.Map} that you may use is the
* adjacency list from {@code graph}. DO NOT create new instances of Map
* for DFS (storing the adjacency list in a variable is fine).
*
* DO NOT modify the structure of the graph. The graph should be unmodified
* after this method terminates.
*
* @throws IllegalArgumentException if any input
* is null, or if {@code start} doesn't exist in the graph
* @param <T> the generic typing of the data
* @param start the vertex to begin the dfs on
* @param graph the graph to search through
* @return list of vertices in visited order
*/
public static <T> List<Vertex<T>> dfs(Vertex<T> start, Graph<T> graph) {

   if(start == null || graph == null){
         throw new IllegalArgumentException("Invalid or null parameters");
   }

   if(!graph.getAdjList().containsKey(start)){
         throw new IllegalArgumentException("Invalid parameters");
   }

   List<Vertex<T>> visitedLst = new ArrayList<>();
   visitedLst.add(start);

   List<VertexDistance<T>> vertexDistances = graph.getAdjList().get(start);
   for (VertexDistance<T> v: vertexDistances) {
         Vertex<T> next = v.getVertex

Graph Algorithms For this assignment, you will be coding 4 differe...