import java.util.*;

/**
 * Your implementation of various different graph algorithms.
 *
 * @author Royce Arockiasamy
 * @userid rarockiasamy6
 * @GTID 903754593
 * @version 1.0
 */
public class GraphAlgorithms {

    /**
     * Performs a breadth first search (bfs) on the input graph, starting at
     * the parameterized starting vertex.
     *
     * When exploring a vertex, explore in the order of neighbors returned by
     * the adjacency list. Failure to do so may cause you to lose points.
     *
     * You may import/use java.util.Set, java.util.List, java.util.Queue, and
     * any classes that implement the aforementioned interfaces, as long as they
     * are efficient.
     *
     * The only instance of java.util.Map that you may use is the
     * adjacency list from 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.
     *
     * @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
     * @throws IllegalArgumentException if any input is null, or if start
     *                                  doesn't exist in the graph
     */
    public static <T> List<Vertex<T>> bfs(Vertex<T> start, Graph<T> graph) {
        if (start == null || graph == null) {
            throw new IllegalArgumentException("Start vertex or graph is null");
        }
        if (!graph.getAdjList().containsKey(start)) {
            throw new IllegalArgumentException("Start vertex doesn't exist in the graph");
        }

        Set<Vertex<T>> visited = new HashSet<>();
        List<Vertex<T>> vertices = new ArrayList<>();
        Queue<Vertex<T>> queue = new LinkedList<>();

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

        while (!queue.isEmpty()) {
            Vertex<T> curr = queue.poll();
            vertices.add(curr);

            for (VertexDistance<T> adj : graph.getAdjList().get(curr)) {
                if (!visited.contains(adj.getVertex())) {
                    queue.add(adj.getVertex());
                    visited.add(adj.getVertex());
                }
            }
        }

        return vertices;
    }

    /**
     * Performs a depth first search (dfs) on the input graph, starting at
     * the parameterized starting vertex.
     *
     * When exploring a vertex, explore in the order of neighbors returned by
     * the adjacency list. Failure to do so may cause you to lose points.
     *
     * *NOTE* You MUST implement this method recursively, or else you will lose
     * all points for this method.
     *
     * You may import/use java.util.Set, java.util.List, and
     * any classes that implement the aforementioned interfaces, as long as they
     * are efficient.
     *
     * The only instance of java.util.Map that you may use is the
     * adjacency list from 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.
     *
     * @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
     * @throws IllegalArgumentException if any input is null, or if start
     *                                  doesn't exist in the graph
     */
    public static <T> List<Vertex<T>> dfs(Vertex<T> start, Graph<T> graph) {
        if (start == null || graph == null) {
            throw new IllegalArgumentException("Start vertex or graph is null");
        }
        if (!graph.getAdjList().containsKey(start)) {
            throw new IllegalArgumentException("Start vertex not in graph");
        }

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

        rDfs(start, graph, list, visited);
        return list;
    }

    /**
     * helper method for the dfs algorithm.
     * @param start dfs starts on this node
     * @param graph graph consisting of all the nodes
     * @param visited set to keep track of visited nodes
     * @param list vertices list
     */
    private static <T> void rDfs(Vertex<T> start, Graph<T> graph, List<Vertex<T>> list, Set<Vertex<T>> visited) {
        visited.add(start);
        list.add(start);
        for (VertexDistance<T> adj : graph.getAdjList().get(start)) {
            if (!visited.contains(adj.getVertex())) {
                rDfs(adj.getVertex(), graph, list, visited);
            }
        }
    }

    /**
     * Finds the single-source shortest distance between the start vertex and
     * all vertices given a weighted graph (you may assume non-negative edge
     * weights).
     *
     * Return a map of the shortest distances such that the key of each entry
     * is a node in the graph and the value for the key is the shortest distance
     * to that node from start, or Integer.MAX_VALUE (representing
     * infinity) if no path exists.
     *
     * You may import/use java.util.PriorityQueue,
     * java.util.Map, and java.util.Set and any class that
     * implements the aforementioned interfaces, as long as your use of it
     * is efficient as possible.
     *
     * You should implement the version of Dijkstra's where you use two
     * termination conditions in conjunction.
     *
     * 1) Check if all of the vertices have been visited.
     * 2) Check if the PQ is empty.
     *
     * DO NOT modify the structure of the graph. The graph should be unmodified
     * after this method terminates.
     *
     * @param <T>   the generic typing of the data
     * @param start the vertex to begin the Dijkstra's on (source)
     * @param graph the graph we are applying Dijkstra's to
     * @return a map of the shortest distances from start to every
     * other node in the graph
     * @throws IllegalArgumentException if any input is null, or if start
     *                                  doesn't exist in the graph.
     */
    public static <T> Map<Vertex<T>, Integer> dijkstras(Vertex<T> start,
                                                        Graph<T> graph) {
        if (start == null || graph == null) {
            throw new IllegalArgumentException("Start vertex or graph is null");
        }
        if (!graph.getVertices().contains(start)) {
            throw new IllegalArgumentException("Start vertex not in graph");
        }

        Set<Vertex<T>> visited = new HashSet<>();
        Map<Vertex<T>, Integer> weights = new HashMap<>();
        PriorityQueue<VertexDistance<T>> priorityQueue = new PriorityQueue<>();

        VertexDistance<T> starter = new VertexDistance<>(start, 0);
        priorityQueue.add(starter);

        for (Vertex<T> vertex : graph.getVertices()) {
            weights.put(vertex, Integer.MAX_VALUE);
        }

        int dist = 0;
        while (!(priorityQueue.isEmpty()) && visited.size() < graph.getVertices().size()) {
            VertexDistance<T> pointer = priorityQueue.poll();
            if (!visited.contains(pointer.getVertex())) {
                dist = pointer.getDistance();
                visited.add(pointer.getVertex());
                weights.put(pointer.getVertex(), dist);
            }
            for (VertexDistance<T> vertex : graph.getAdjList().get(pointer.getVertex())) {
                if (!visited.contains(vertex.getVertex())) {
                    VertexDistance<T> temp = new VertexDistance<>(vertex.getVertex(),
                            dist + vertex.getDistance());
                    priorityQueue.add(temp);
                }
            }
        }

        return weights;
    }

    /**
     * Runs Prim's algorithm on the given graph and returns the Minimum
     * Spanning Tree (MST) in the form of a set of Edges. If the graph is
     * disconnected and therefore no valid MST exists, return null.
     *
     * You may assume that the passed in graph is undirected. In this framework,
     * this means that if (u, v, 3) is in the graph, then the opposite edge
     * (v, u, 3) will also be in the graph, though as a separate Edge object.
     *
     * The returned set of edges should form an undirected graph. This means
     * that every time you add an edge to your return set, you should add the
     * reverse edge to the set as well. This is for testing purposes. This
     * reverse edge does not need to be the one from the graph itself; you can
     * just make a new edge object representing the reverse edge.
     *
     * You may assume that there will only be one valid MST that can be formed.
     *
     * You should NOT allow self-loops or parallel edges in the MST.
     *
     * You may import/use PriorityQueue, java.util.Set, and any class that 
     * implements the aforementioned interface.
     *
     * DO NOT modify the structure of the graph. The graph should be unmodified
     * after this method terminates.
     *
     * The only instance of java.util.Map that you may use is the
     * adjacency list from graph. DO NOT create new instances of Map
     * for this method (storing the adjacency list in a variable is fine).
     *
     * @param <T> the generic typing of the data
     * @param start the vertex to begin Prims on
     * @param graph the graph we are applying Prims to
     * @return the MST of the graph or null if there is no valid MST
     * @throws IllegalArgumentException if any input is null, or if start
     *                                  doesn't exist in the graph.
     */
    public static <T> Set<Edge<T>> prims(Vertex<T> start, Graph<T> graph) {
        if (start == null) {
            throw new IllegalArgumentException("The start vertex is null");
        }
        if (graph == null) {
            throw new IllegalArgumentException("The graph is null");
        }
        if (!graph.getVertices().contains(start)) {
            throw new IllegalArgumentException("The start is not in the graph");
        }
        Set<Vertex<T>> visited = new HashSet<>();
        Set<Edge<T>> edgeSet = new HashSet<>();
        PriorityQueue<Edge<T>> pq = new PriorityQueue<>();
        Map<Vertex<T>, List<VertexDistance<T>>> adjList = graph.getAdjList();

        for (VertexDistance<T> v : adjList.get(start)) {
            Edge<T> curr = new Edge<>(start, v.getVertex(), v.getDistance());
            pq.add(curr);
        }
        visited.add(start);
        while (!pq.isEmpty() && visited.size() < graph.getVertices().size()) {
            Edge<T> curr = pq.poll();
            if (!visited.contains(curr.getV())) {
                visited.add(curr.getV());
                Edge<T> edge = new Edge<>(curr.getU(), curr.getV(), curr.getWeight());
                edgeSet.add(edge);
                Edge<T> edge1 = new Edge<>(curr.getV(), curr.getU(), curr.getWeight());
                edgeSet.add(edge1);
                for (VertexDistance<T> vx : adjList.get(curr.getV())) {
                    if (!visited.contains(vx.getVertex())) {
                        Edge<T> pointer = new Edge<>(curr.getV(), vx.getVertex(), vx.getDistance());
                        pq.add(pointer);
                    }
                }
            }
        }
        if (edgeSet.size() < graph.getVertices().size() - 1) {
            return null;
        }
        return edgeSet;
    }
}

correct the code for prim's algorithm and only gimme code for that