## Saturday, November 28, 2015

### Prim's Algorithm : Eager Implementation using Fibonacci Heap - Java

Fibonacci Heap source from : http://graphstream-project.org/api/gs-algo/org/graphstream/algorithm/util/FibonacciHeap.html#decreaseKey(org.graphstream.algorithm.util.FibonacciHeap.Node, K)

Eager Implementation :

```import java.util.ArrayList;
import org.graphstream.algorithm.util.FibonacciHeap;

public class PrimsEager {
boolean marked[];
ArrayList<ArrayList<Edge>> graph;
ArrayList<Edge> mst;

double distTo[];
int edgeTo[];

int E, V;

PrimsEager(int v){
V = v;
graph = new ArrayList<>();
distTo = new double[V];
edgeTo = new int[V];
mst = new ArrayList<>();
marked = new boolean[V];
}

public void applyPrims(int start){
marked[start] = true;
distTo[start] = 0;
FibonacciHeap<Double, Integer> pq = new FibonacciHeap<>();
FibonacciHeap.Node nodes[] = new FibonacciHeap.Node[V];
nodes[start] = n;

while(!pq.isEmpty()){
int node = pq.extractMin();

/*
The statement below is necessary, otherwise
some node may wrongly update the new shorter path
for a node that has been already processed and
discarded from the priority queue. (Node 3 in this graph, for example.)
*/

System.out.println("\nRemoved "+node);

for(Edge w:graph.get(node)){
int V = w.other(node);
if(!marked[V]){
marked[V] = true;

/*
Save the reference to the PriorityQueue Node so that
decreaseKey can be performed
*/

/*
distance to the nearest MST node.
*/
distTo[V] = w.weight();

/*
what node is it.
*/
edgeTo[V] = node;

System.out.println("\nSet distTo["+V+"] to "+distTo[V]);
}else if(!checkAddedNode[V] && distTo[V] > w.weight()){
//A better path to this node has been found
//Need to update (decrease) priority (distanceTo value)

System.out.println("\n V = "+V+" old = "+distTo[V]+" new = "+w.weight());
//
distTo[V] = w.weight();

System.out.println("distTo["+V+"] = "+distTo[V]+" new value = "+distTo[V]);

pq.decreaseKey(nodes[V], distTo[V]);
edgeTo[V] = node;

System.out.println("edgeTo["+V+"] = "+node);
}
}
}

System.out.println("MST Edges : ");
for(int i=0;i<V;++i){
if(i==start)continue;
System.out.println(i+" - "+edgeTo[i]);
}
}

public void addEdge(int v, int w, double weight){
Edge e = new Edge(v, w, weight);
E++;
}

public static void main(String[] args){
PrimsEager prims = new PrimsEager(8);

prims.applyPrims(0);
}
}
```

Output :

Removed 0

Set distTo[7] to 0.16

Set distTo[2] to 0.26

Set distTo[4] to 0.38

Set distTo[6] to 0.58

Removed 7

Set distTo[1] to 0.19

Set distTo[5] to 0.28

V = 4 old = 0.38 new = 0.37
distTo[4] = 0.37 new value = 0.37
edgeTo[4] = 7

Removed 1

Set distTo[3] to 0.29

Removed 2

V = 3 old = 0.29 new = 0.17
distTo[3] = 0.17 new value = 0.17
edgeTo[3] = 2

V = 6 old = 0.58 new = 0.4
distTo[6] = 0.4 new value = 0.4
edgeTo[6] = 2

Removed 3

Removed 5

V = 4 old = 0.37 new = 0.35
distTo[4] = 0.35 new value = 0.35
edgeTo[4] = 5

Removed 4

Removed 6
MST Edges :
1 - 7
2 - 0
3 - 2
4 - 5
5 - 7
6 - 2
7 - 0