 # What is the easiest way to implement prim's algorithm in java?

I tried to implement prim’s algorithm in java but I found it difficult to implement. Can any one help me to implement prim’s algorithm using built in data structure(Collections framework)

For starters you can have a look at the following links:-

Prims code in java

Java prims implementation

you can have a look at both the links but, i think this would not work for extremely large data sets as both of the codes maintain a adjacency matrix for the graph, for large data sets you have to maintain either a 2-D pair or a vector of pairs

Here’s the code
import java.util.*;

public class PRIMS {

``````static class EDGE{
int from, to;
double weight;

EDGE(int f, int t, double w){
from = f;
to = t;
weight = w;
}
}

public static ArrayList<EDGE> prims(ArrayList<ArrayList<EDGE>> G){
if(G.isEmpty())throw new NullPointerException("The Graph is empty");

ArrayList<EDGE> mst = new ArrayList<>();
PriorityQueue<EDGE> pq = new PriorityQueue<>((Object o1, Object o2) -> {
EDGE first = (EDGE)o1;
EDGE second = (EDGE)o2;

if(first.weight<second.weight)return -1;
else if(first.weight>second.weight)return 1;
else return 0;
});

for(EDGE e:G.get(0)){
}

boolean[] marked = new boolean[G.size()];
marked = true;
while(!pq.isEmpty()){
EDGE e = pq.peek();

pq.poll();
if(marked[e.from] && marked[e.to])continue;
marked[e.from] = true;
for(EDGE edge:G.get(e.to)){
if(!marked[edge.to]){
}
}
marked[e.to] = true;

}
return mst;
}

public static ArrayList<ArrayList<EDGE>> createGraph(EDGE[] edges){
ArrayList<ArrayList<EDGE>> G = new ArrayList<>();
int length = edges.length*2;
for(int i=0;i<length;++i){
}

for(EDGE e:edges){
EDGE other = new EDGE(e.to, e.from, e.weight);
System.out.println("Added edge ["+e.from+", "+e.to+" : "+e.weight+"] "+"["+e.to+", "+e.from+" : "+e.weight+"]");
}

return G;
}

public static void main(String[] args){
EDGE[] edges = new EDGE;

edges = new EDGE(0, 7, 0.16);
edges = new EDGE(2, 3, 0.17);
edges = new EDGE(1, 7, 0.19);
edges = new EDGE(0, 2, 0.26);

edges = new EDGE(5, 7, 0.28);
edges = new EDGE(1, 3, 0.29);
edges = new EDGE(1, 5, 0.32);
edges = new EDGE(2, 7, 0.34);

edges = new EDGE(4, 5, 0.35);
edges = new EDGE(1, 2, 0.36);
edges = new EDGE(4, 7, 0.37);
edges = new EDGE(0, 4, 0.38);

edges = new EDGE(6, 2, 0.40);
edges = new EDGE(3, 6, 0.52);
edges = new EDGE(6, 0, 0.58);
edges = new EDGE(6, 4, 0.93);

ArrayList<ArrayList<EDGE>> graph = createGraph(edges);
ArrayList<EDGE> mst = prims(graph);

System.out.println("MST: ");
for(EDGE e:mst){
System.out.println(e.from+" - "+e.to+" : "+e.weight);
}
}
``````

}

//