import java.util.HashSet; import java.util.Map; import java.util.PriorityQueue; import java.util.Queue; import java.util.Set; /** * Your implementation of Prim's algorithm. */ public class...

Implement prim's algorithm


import java.util.HashSet; import java.util.Map; import java.util.PriorityQueue; import java.util.Queue; import java.util.Set; /** * Your implementation of Prim's algorithm. */ public class GraphAlgorithms { /** * 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 java.util.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). * * You may assume that the passed in start vertex and graph will not be null. * You may assume that the start vertex exists in the graph. * * @param 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. */ public static Set<>> prims(Vertex start, Graph graph) { // WRITE YOUR CODE HERE (DO NOT MODIFY METHOD HEADER)! if (graph == null) { throw new IllegalArgumentException("Graph can not be null."); } PriorityQueue<>> queue = new PriorityQueue<>(); Iterator<>> it = graph.getVertices().iterator(); Set<>> msf = new HashSet<>(); Set<>> visitedVertices = new HashSet<>(); while (it.hasNext() && msf.size() < 2="" *="" graph.getvertices().size()="" -="" 2)="" {=""> startingVertex = it.next(); if (!visitedVertices.contains(startingVertex)) { queue.clear(); queue.addAll(graph.getAdjList().get(startingVertex)); visitedVertices.add(startingVertex); while (!queue.isEmpty() && msf.size() < 2="" *="" graph.getvertices().size()="" -="" 1)="" {=""> currentEdge = queue.poll(); if (!(visitedVertices.contains(currentEdge.getV()) && visitedVertices.contains(currentEdge.getU()))) { msf.add(currentEdge); for (Edge edge : graph.getAdjList().get(currentEdge.getV())) { if (edge.getV().equals(currentEdge.getU())) { // if current edge is a-->d // add d-->a to minimum spanning tree msf.add(edge); } else { queue.add(edge); } } visitedVertices.add(currentEdge.getV()); } } } } return msf; } }