I found this primMST java class source code online for the prim algorithm. It was accompanied...
I found this primMST java class source code online for the prim algorithm. It was accompanied by another class called BinaryMinHeap, which is used in the primMST class. I copied and pasted the primMST code in NetBeans, and it gave me error labels in the text editor for three classes that were used in the primMST class. They are class Edge, Graph, and Vertex.
There was another error for class List, but I fixed that by using
the import statement import java.util.*;
Is there an import statement for the class called "Edge", "Graph",
and "Vertex"? I've been searching google but I couldn't find
anything. Below is the source code for primMST class.
package mst;
import java.util.*;
/**
*
* @author
*/
public class PrimMST {
/**
* Main method of Prim's algorithm.
*/
public List> primMST(Graph graph){
//binary heap + map data structure
BinaryMinHeap> minHeap = new BinaryMinHeap<>();
//map of vertex to edge which gave minimum weight to this
vertex.
Map,Edge> vertexToEdge = new HashMap<>();
//stores final result
List> result = new ArrayList<>();
//insert all vertices with infinite value initially.
for(Vertex v : graph.getAllVertex()){
minHeap.add(Integer.MAX_VALUE, v);
}
//start from any random vertex
Vertex startVertex = graph.getAllVertex().iterator().next();
//for the start vertex decrease the value in heap + map to
0
minHeap.decrease(startVertex, 0);
//iterate till heap + map has elements in it
while(!minHeap.empty()){
//extract min value vertex from heap + map
Vertex current = minHeap.extractMin();
//get the corresponding edge for this vertex if present and add
it to final result.
//This edge wont be present for first vertex.
Edge spanningTreeEdge = vertexToEdge.get(current);
if(spanningTreeEdge != null) {
result.add(spanningTreeEdge);
}
//iterate through all the adjacent vertices
for(Edge edge : current.getEdges()){
Vertex adjacent = getVertexForEdge(current, edge);
//check if adjacent vertex exist in heap + map and weight attached
with this vertex is greater than this edge weight
if(minHeap.containsData(adjacent) &&
minHeap.getWeight(adjacent) > edge.getWeight()){
//decrease the value of adjacent vertex to this edge weight.
minHeap.decrease(adjacent, edge.getWeight());
//add vertex->edge mapping in the graph.
vertexToEdge.put(adjacent, edge);
}
}
}
return result;
} // end of primMST
private Vertex getVertexForEdge(Vertex v, Edge e){
return e.getVertex1().equals(v) ? e.getVertex2() :
e.getVertex1();
}
} // end of PrimMST class
Homework Answers
Please find my code.
Please let me know in case of any issue.
#############################
import java.util.ArrayList;
import java.util.Collection;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class Graph<T>{
private List<Edge<T>> allEdges;
private Map<Long,Vertex<T>> allVertex;
boolean isDirected = false;
public Graph(boolean isDirected){
allEdges = new ArrayList<Edge<T>>();
allVertex = new HashMap<Long,Vertex<T>>();
this.isDirected = isDirected;
}
public void addEdge(long id1, long id2){
addEdge(id1,id2,0);
}
//This works only for directed graph because for undirected graph we can end up
//adding edges two times to allEdges
public void addVertex(Vertex<T> vertex){
if(allVertex.containsKey(vertex.getId())){
return;
}
allVertex.put(vertex.getId(), vertex);
for(Edge<T> edge : vertex.getEdges()){
allEdges.add(edge);
}
}
public Vertex<T> addSingleVertex(long id){
if(allVertex.containsKey(id)){
return allVertex.get(id);
}
Vertex<T> v = new Vertex<T>(id);
allVertex.put(id, v);
return v;
}
public Vertex<T> getVertex(long id){
return allVertex.get(id);
}
public void addEdge(long id1,long id2, int weight){
Vertex<T> vertex1 = null;
if(allVertex.containsKey(id1)){
vertex1 = allVertex.get(id1);
}else{
vertex1 = new Vertex<T>(id1);
allVertex.put(id1, vertex1);
}
Vertex<T> vertex2 = null;
if(allVertex.containsKey(id2)){
vertex2 = allVertex.get(id2);
}else{
vertex2 = new Vertex<T>(id2);
allVertex.put(id2, vertex2);
}
Edge<T> edge = new Edge<T>(vertex1,vertex2,isDirected,weight);
allEdges.add(edge);
vertex1.addAdjacentVertex(edge, vertex2);
if(!isDirected){
vertex2.addAdjacentVertex(edge, vertex1);
}
}
public List<Edge<T>> getAllEdges(){
return allEdges;
}
public Collection<Vertex<T>> getAllVertex(){
return allVertex.values();
}
public void setDataForVertex(long id, T data){
if(allVertex.containsKey(id)){
Vertex<T> vertex = allVertex.get(id);
vertex.setData(data);
}
}
@Override
public String toString(){
StringBuffer buffer = new StringBuffer();
for(Edge<T> edge : getAllEdges()){
buffer.append(edge.getVertex1() + " " + edge.getVertex2() + " " + edge.getWeight());
buffer.append("\n");
}
return buffer.toString();
}
}
class Vertex<T> {
long id;
private T data;
private List<Edge<T>> edges = new ArrayList<>();
private List<Vertex<T>> adjacentVertex = new ArrayList<>();
Vertex(long id){
this.id = id;
}
public long getId(){
return id;
}
public void setData(T data){
this.data = data;
}
public T getData(){
return data;
}
public void addAdjacentVertex(Edge<T> e, Vertex<T> v){
edges.add(e);
adjacentVertex.add(v);
}
public String toString(){
return String.valueOf(id);
}
public List<Vertex<T>> getAdjacentVertexes(){
return adjacentVertex;
}
public List<Edge<T>> getEdges(){
return edges;
}
public int getDegree(){
return edges.size();
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + (int) (id ^ (id >>> 32));
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Vertex other = (Vertex) obj;
if (id != other.id)
return false;
return true;
}
}
class Edge<T>{
private boolean isDirected = false;
private Vertex<T> vertex1;
private Vertex<T> vertex2;
private int weight;
Edge(Vertex<T> vertex1, Vertex<T> vertex2){
this.vertex1 = vertex1;
this.vertex2 = vertex2;
}
Edge(Vertex<T> vertex1, Vertex<T> vertex2,boolean isDirected,int weight){
this.vertex1 = vertex1;
this.vertex2 = vertex2;
this.weight = weight;
this.isDirected = isDirected;
}
Edge(Vertex<T> vertex1, Vertex<T> vertex2,boolean isDirected){
this.vertex1 = vertex1;
this.vertex2 = vertex2;
this.isDirected = isDirected;
}
Vertex<T> getVertex1(){
return vertex1;
}
Vertex<T> getVertex2(){
return vertex2;
}
int getWeight(){
return weight;
}
public boolean isDirected(){
return isDirected;
}
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((vertex1 == null) ? 0 : vertex1.hashCode());
result = prime * result + ((vertex2 == null) ? 0 : vertex2.hashCode());
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Edge other = (Edge) obj;
if (vertex1 == null) {
if (other.vertex1 != null)
return false;
} else if (!vertex1.equals(other.vertex1))
return false;
if (vertex2 == null) {
if (other.vertex2 != null)
return false;
} else if (!vertex2.equals(other.vertex2))
return false;
return true;
}
@Override
public String toString() {
return "Edge [isDirected=" + isDirected + ", vertex1=" + vertex1
+ ", vertex2=" + vertex2 + ", weight=" + weight + "]";
}
}
#################################
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class BinaryMinHeap<T> {
private List<Node> allNodes = new ArrayList<>();
private Map<T,Integer> nodePosition = new HashMap<>();
public class Node {
int weight;
T key;
}
/**
* Checks where the key exists in heap or not
*/
public boolean containsData(T key){
return nodePosition.containsKey(key);
}
/**
* Add key and its weight to they heap
*/
public void add(int weight,T key) {
Node node = new Node();
node.weight = weight;
node.key = key;
allNodes.add(node);
int size = allNodes.size();
int current = size - 1;
int parentIndex = (current - 1) / 2;
nodePosition.put(node.key, current);
while (parentIndex >= 0) {
Node parentNode = allNodes.get(parentIndex);
Node currentNode = allNodes.get(current);
if (parentNode.weight > currentNode.weight) {
swap(parentNode,currentNode);
updatePositionMap(parentNode.key,currentNode.key,parentIndex,current);
current = parentIndex;
parentIndex = (parentIndex - 1) / 2;
} else {
break;
}
}
}
/**
* Get the heap min without extracting the key
*/
public T min(){
return allNodes.get(0).key;
}
/**
* Checks with heap is empty or not
*/
public boolean empty(){
return allNodes.size() == 0;
}
/**
* Decreases the weight of given key to newWeight
*/
public void decrease(T data, int newWeight){
Integer position = nodePosition.get(data);
allNodes.get(position).weight = newWeight;
int parent = (position -1 )/2;
while(parent >= 0){
if(allNodes.get(parent).weight > allNodes.get(position).weight){
swap(allNodes.get(parent), allNodes.get(position));
updatePositionMap(allNodes.get(parent).key,allNodes.get(position).key,parent,position);
position = parent;
parent = (parent-1)/2;
}else{
break;
}
}
}
/**
* Get the weight of given key
*/
public Integer getWeight(T key) {
Integer position = nodePosition.get(key);
if( position == null ) {
return null;
} else {
return allNodes.get(position).weight;
}
}
/**
* Returns the min node of the heap
*/
public Node extractMinNode() {
int size = allNodes.size() -1;
Node minNode = new Node();
minNode.key = allNodes.get(0).key;
minNode.weight = allNodes.get(0).weight;
int lastNodeWeight = allNodes.get(size).weight;
allNodes.get(0).weight = lastNodeWeight;
allNodes.get(0).key = allNodes.get(size).key;
nodePosition.remove(minNode.key);
nodePosition.remove(allNodes.get(0));
nodePosition.put(allNodes.get(0).key, 0);
allNodes.remove(size);
int currentIndex = 0;
size--;
while(true){
int left = 2*currentIndex + 1;
int right = 2*currentIndex + 2;
if(left > size){
break;
}
if(right > size){
right = left;
}
int smallerIndex = allNodes.get(left).weight <= allNodes.get(right).weight ? left : right;
if(allNodes.get(currentIndex).weight > allNodes.get(smallerIndex).weight){
swap(allNodes.get(currentIndex), allNodes.get(smallerIndex));
updatePositionMap(allNodes.get(currentIndex).key,allNodes.get(smallerIndex).key,currentIndex,smallerIndex);
currentIndex = smallerIndex;
}else{
break;
}
}
return minNode;
}
/**
* Extract min value key from the heap
*/
public T extractMin(){
Node node = extractMinNode();
return node.key;
}
private void printPositionMap(){
System.out.println(nodePosition);
}
private void swap(Node node1,Node node2){
int weight = node1.weight;
T data = node1.key;
node1.key = node2.key;
node1.weight = node2.weight;
node2.key = data;
node2.weight = weight;
}
private void updatePositionMap(T data1, T data2, int pos1, int pos2){
nodePosition.remove(data1);
nodePosition.remove(data2);
nodePosition.put(data1, pos1);
nodePosition.put(data2, pos2);
}
public void printHeap(){
for(Node n : allNodes){
System.out.println(n.weight + " " + n.key);
}
}
public static void main(String args[]){
BinaryMinHeap<String> heap = new BinaryMinHeap<String>();
heap.add(3, "Tushar");
heap.add(4, "Ani");
heap.add(8, "Vijay");
heap.add(10, "Pramila");
heap.add(5, "Roy");
heap.add(6, "NTF");
heap.add(2,"AFR");
heap.decrease("Pramila", 1);
heap.printHeap();
heap.printPositionMap();
}
}
######################
import java.util.*;
public class PrimMST {
/**
* Main method of Prim's algorithm.
*/
public List<Edge<Integer>> primMST(Graph<Integer> graph){
//binary heap + map data structure
BinaryMinHeap<Vertex<Integer>> minHeap = new BinaryMinHeap<>();
//map of vertex to edge which gave minimum weight to this vertex.
Map<Vertex<Integer>,Edge<Integer>> vertexToEdge = new HashMap<>();
//stores final result
List<Edge<Integer>> result = new ArrayList<>();
//insert all vertices with infinite value initially.
for(Vertex<Integer> v : graph.getAllVertex()){
minHeap.add(Integer.MAX_VALUE, v);
}
//start from any random vertex
Vertex<Integer> startVertex = graph.getAllVertex().iterator().next();
//for the start vertex decrease the value in heap + map to 0
minHeap.decrease(startVertex, 0);
//iterate till heap + map has elements in it
while(!minHeap.empty()){
//extract min value vertex from heap + map
Vertex<Integer> current = minHeap.extractMin();
//get the corresponding edge for this vertex if present and add it to final result.
//This edge wont be present for first vertex.
Edge<Integer> spanningTreeEdge = vertexToEdge.get(current);
if(spanningTreeEdge != null) {
result.add(spanningTreeEdge);
}
//iterate through all the adjacent vertices
for(Edge<Integer> edge : current.getEdges()){
Vertex<Integer> adjacent = getVertexForEdge(current, edge);
//check if adjacent vertex exist in heap + map and weight attached with this vertex is greater than this edge weight
if(minHeap.containsData(adjacent) && minHeap.getWeight(adjacent) > edge.getWeight()){
//decrease the value of adjacent vertex to this edge weight.
minHeap.decrease(adjacent, edge.getWeight());
//add vertex->edge mapping in the graph.
vertexToEdge.put(adjacent, edge);
}
}
}
return result;
}
private Vertex<Integer> getVertexForEdge(Vertex<Integer> v, Edge<Integer> e){
return e.getVertex1().equals(v) ? e.getVertex2() : e.getVertex1();
}
public static void main(String args[]){
Graph<Integer> graph = new Graph<>(false);
/* graph.addEdge(0, 1, 4);
graph.addEdge(1, 2, 8);
graph.addEdge(2, 3, 7);
graph.addEdge(3, 4, 9);
graph.addEdge(4, 5, 10);
graph.addEdge(2, 5, 4);
graph.addEdge(1, 7, 11);
graph.addEdge(0, 7, 8);
graph.addEdge(2, 8, 2);
graph.addEdge(3, 5, 14);
graph.addEdge(5, 6, 2);
graph.addEdge(6, 8, 6);
graph.addEdge(6, 7, 1);
graph.addEdge(7, 8, 7);*/
graph.addEdge(1, 2, 3);
graph.addEdge(2, 3, 1);
graph.addEdge(3, 1, 1);
graph.addEdge(1, 4, 1);
graph.addEdge(2, 4, 3);
graph.addEdge(4, 5, 6);
graph.addEdge(5, 6, 2);
graph.addEdge(3, 5, 5);
graph.addEdge(3, 6, 4);
PrimMST prims = new PrimMST();
Collection<Edge<Integer>> edges = prims.primMST(graph);
for(Edge<Integer> edge : edges){
System.out.println(edge);
}
}
}
Add Answer to:
I found this primMST java class source code online for the prim
algorithm. It was accompanied...
Given the following weighted graph G. use Prim's algorithm to determine the Minimum-Cost Spanning Tree (MCST)...
Given the following weighted graph G. use Prim's algorithm to determine the Minimum-Cost Spanning Tree (MCST) with node 1 as the "root". List the vertices in the order in which the algorithm adds them to the solution, along with the edge and its weight used to make the selection, one per line. Each line should look like this: add vertex y: edge = (x,y), weight = 5 When the algorithm ends there are, generally, edges left in the heap. List...
need help filling in the code def prim(G): Use Prim's algorithm to find a MST for the graph G … # Initialize tree T with a single vertex and no edges v = next(iter( )) # while the vertex set of T...
need help filling in the code
def prim(G): Use Prim's algorithm to find a MST for the graph G … # Initialize tree T with a single vertex and no edges v = next(iter( )) # while the vertex set of T is smaller than the v+tex set of G, # (i.e. while the vertex set of T is a proper subset of the vertex set of G), find the edge e with minimum weight so that # Tte is...
Consider the java Graph class below which represents an undirected graph in an adjacency list. How...
Consider the java Graph class below which represents an undirected graph in an adjacency list. How would you add a method to delete an edge from the graph? // Exercise 4.1.3 (Solution published at http://algs4.cs.princeton.edu/) package algs41; import stdlib.*; import algs13.Bag; /** * The <code>Graph</code> class represents an undirected graph of vertices * named 0 through V-1. * It supports the following operations: add an edge to the graph, * iterate over all of the neighbors adjacent to a vertex....
Help !! I need help with Depth-First Search using an undirected graph. Write a program, IN JAVA, ...
Help !! I need help with Depth-First Search using an
undirected graph.
Write a program, IN JAVA, to implement the
depth-first search algorithm using the pseudocode given.
Write a driver program, which reads input file mediumG.txt as an
undirected graph and runs
the depth-first search algorithm to find paths to all the other
vertices considering 0 as the
source. This driver program should display the paths in the
following manner:
0 to ‘v’: list of all the vertices traversed to...
C++ Questions: 4) A graph-traversal algorithm stops when it ______. a) first encounters the designated destination...
C++ Questions: 4) A graph-traversal algorithm stops when it ______. a) first encounters the designated destination vertex b) has visited all the vertices that it can reach c) has visited all the vertices d) has visited all the vertices and has returned to the origin vertex 5) In the following STL declaration of an adjacency list, what does the map pair represent? a) vector<map<int, int> >adjList; b) the first vertex (key) and the edge weight (value) c) the second vertex...
In this problem, you are expected to implement Prim's Algorithm on an undirected simple graph. Write...
In this problem, you are expected to implement Prim's Algorithm on an undirected simple graph. Write a method that is part of a class that implements Graph as an adjacency matrix. This method should generate a minimum spanning tree using Prim's Algorithm, and print out the edge added by the algorithm on each iteration. 3 10 4 8 Output: 1 2 1 3 34 35 5 6 17 3 12 34 5 1 6 8 20 4 Output: 26 65...
How would I traverse through this graph? Provide example code, please! class Edge { int src,...
How would I traverse through this graph? Provide example code, please! class Edge { int src, dest; Edge(int src, int dest) { this.src = src; this.dest = dest; } }; // class to represent a graph object class Graph { // A list of lists to represent adjacency list List<List<Integer>> adj = new ArrayList<>(); // Constructor to construct graph public Graph(List<Edge> edges) { // allocate memory for adjacency list for (int i = 0; i < edges.size(); i++) { adj.add(i,...
from collections import defaultdict # This class represents a directed graph using # adjacency list...
from collections import defaultdict # This class represents a directed graph using # adjacency list representation class Graph: # Constructor def __init__(self): # default dictionary to store graph self.graph = defaultdict(list) # function to add an edge to graph def addEdge(self,u,v): self.graph[u].append(v) # Function to print a BFS of graph def BFS(self, s): # Mark all the vertices as not visited visited = [False] * (len(self.graph)) # Create a queue for BFS queue...
Below is the Graph file that needs to be modified(using Python3) : #!/usr/bin/python3 # Simple Vertex...
Below is the Graph file that
needs to be modified(using Python3) :
#!/usr/bin/python3
# Simple Vertex class
class Vertex:
""" Lightweight vertex structure for a graph.
Vertices can have the following labels:
UNEXPLORED
VISITED
Assuming the element of a vertex is string type
"""
__slots__ = '_element', '_label'
def __init__(self, element, label="UNEXPLORED"):
""" Constructor. """
self._element = element
self._label = label
def element(self):
""" Return element associated with this vertex. """
return self._element
def getLabel(self):
""" Get label assigned to...
I have a Graph.java which I need to complete four methods in the java file: completeGraph(),...
I have a Graph.java which I need to complete four methods in the java file: completeGraph(), valence(int vid), DFS(int start), and findPathBFS(int start, int end). I also have a JUnit test file GraphTest.java for you to check your code. Here is Graph.java: import java.util.ArrayList; import java.util.LinkedList; import java.util.Queue; import java.util.Stack; /* Generic vertex class */ class Vertex<T> { public T data; public boolean visited; public Vertex() { data = null; visited = false; } public Vertex(T _data) { data =...
Given the following weighted graph G. use Prim's algorithm to determine the Minimum-Cost Spanning Tree (MCST) with node 1 as the "root". List the vertices in the order in which the algorithm adds them to the solution, along with the edge and its weight used to make the selection, one per line. Each line should look like this: add vertex y: edge = (x,y), weight = 5 When the algorithm ends there are, generally, edges left in the heap. List...
need help filling in the code
def prim(G): Use Prim's algorithm to find a MST for the graph G … # Initialize tree T with a single vertex and no edges v = next(iter( )) # while the vertex set of T is smaller than the v+tex set of G, # (i.e. while the vertex set of T is a proper subset of the vertex set of G), find the edge e with minimum weight so that # Tte is...
Help !! I need help with Depth-First Search using an
undirected graph.
Write a program, IN JAVA, to implement the
depth-first search algorithm using the pseudocode given.
Write a driver program, which reads input file mediumG.txt as an
undirected graph and runs
the depth-first search algorithm to find paths to all the other
vertices considering 0 as the
source. This driver program should display the paths in the
following manner:
0 to ‘v’: list of all the vertices traversed to...
In this problem, you are expected to implement Prim's Algorithm on an undirected simple graph. Write a method that is part of a class that implements Graph as an adjacency matrix. This method should generate a minimum spanning tree using Prim's Algorithm, and print out the edge added by the algorithm on each iteration. 3 10 4 8 Output: 1 2 1 3 34 35 5 6 17 3 12 34 5 1 6 8 20 4 Output: 26 65...
Below is the Graph file that
needs to be modified(using Python3) :
#!/usr/bin/python3
# Simple Vertex class
class Vertex:
""" Lightweight vertex structure for a graph.
Vertices can have the following labels:
UNEXPLORED
VISITED
Assuming the element of a vertex is string type
"""
__slots__ = '_element', '_label'
def __init__(self, element, label="UNEXPLORED"):
""" Constructor. """
self._element = element
self._label = label
def element(self):
""" Return element associated with this vertex. """
return self._element
def getLabel(self):
""" Get label assigned to...
Most questions answered within 3 hours.
-
Why is the answer b), for this question? I came up with C) for
my incorrect...
asked 2 minutes ago -
Suppose that you know that in the population of full-time
employees in the United States, the...
asked 24 minutes ago -
This experiment was designed originally to sample various meat and carcass quality
aspects of Ontario pigs...
asked 25 minutes ago -
Dopamine Hydrochloride: draw the structure And Show the
functional groups in different colors and label the...
asked 17 minutes ago -
A rope supports a 10 kg dumbbell hanging from it. What is the
tension in the...
asked 16 minutes ago -
) Raw materials are studied for contamination. Suppose that
the number of particles of contamination per...
asked 39 minutes ago -
After running a regression analysis we calculated an F test and
the significance level was 0.15....
asked 35 minutes ago -
----Can someone please help me solve this one using JAVA
----I thank you in advance
Create...
asked 39 minutes ago -
1. What force primarily attracts the potassium ion to
the nitrate ion?
a. London forces...
asked 41 minutes ago -
What are the negative effects of abruptly stopping the use of
all fossil fuels? Give at...
asked 48 minutes ago -
Given that many conflict are the result of different parties having
different interests, is it possible...
asked 53 minutes ago -
A 750 g block can slide uniformly along the horizontal track
when a string attached to...
asked 56 minutes ago