## Monday, June 1, 2015

### Prims Algorithm Java Implementation (Using java.util.PriorityQueue)

Use Prims algorithm for - less nodes, large number of edges
Use Kruskal's algorithm for - more nodes, less edges (http://www.codebytes.in/2015/03/kruskals-algorithm-implementation-in.html)

Source:

```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[0] = 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[16];

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

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

edges[8] = new EDGE(4, 5, 0.35);
edges[9] = new EDGE(1, 2, 0.36);
edges[10] = new EDGE(4, 7, 0.37);
edges[11] = new EDGE(0, 4, 0.38);

edges[12] = new EDGE(6, 2, 0.40);
edges[13] = new EDGE(3, 6, 0.52);
edges[14] = new EDGE(6, 0, 0.58);
edges[15] = 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);
}
}
}```

Output:

Added edge [0, 7 : 0.16] [7, 0 : 0.16]
Added edge [2, 3 : 0.17] [3, 2 : 0.17]
Added edge [1, 7 : 0.19] [7, 1 : 0.19]
Added edge [0, 2 : 0.26] [2, 0 : 0.26]
Added edge [5, 7 : 0.28] [7, 5 : 0.28]
Added edge [1, 3 : 0.29] [3, 1 : 0.29]
Added edge [1, 5 : 0.32] [5, 1 : 0.32]
Added edge [2, 7 : 0.34] [7, 2 : 0.34]
Added edge [4, 5 : 0.35] [5, 4 : 0.35]
Added edge [1, 2 : 0.36] [2, 1 : 0.36]
Added edge [4, 7 : 0.37] [7, 4 : 0.37]
Added edge [0, 4 : 0.38] [4, 0 : 0.38]
Added edge [6, 2 : 0.4] [2, 6 : 0.4]
Added edge [3, 6 : 0.52] [6, 3 : 0.52]
Added edge [6, 0 : 0.58] [0, 6 : 0.58]
Added edge [6, 4 : 0.93] [4, 6 : 0.93]
MST:
0 - 7 : 0.16
7 - 1 : 0.19
0 - 2 : 0.26
2 - 3 : 0.17
7 - 5 : 0.28
5 - 4 : 0.35
2 - 6 : 0.4