package Graph;

public class PrimMSTUsingMatrix {

private boolean[] visited;

private double[] distTo;

private int[] pathTo;

private int numberOfVerticesInMST;

public PrimMSTUsingMatrix(WeightedEdgeGraph g) {

numberOfVerticesInMST = g.V() - 1;

visited = new boolean[g.V()];

distTo = new double[g.V()];

pathTo = new int[g.V()];

for (int v = 0; v < g.V(); v++) {

distTo[v] = Double.MAX_VALUE;

}

distTo[0] = 0.0;

mstUsingMatrix(g);

}

public void mstUsingMatrix(WeightedEdgeGraph g) {

for (int count = 0; count < numberOfVerticesInMST; count++) {

int v = getMinWeightIndex(g.V());

visited[v] = true;

for (int w = 0; w < g.V(); w++) {

if (!visited[w] && g.matrix()[v][w] < distTo[w]) {

pathTo[w] = v;

distTo[w] = g.matrix()[v][w];

}

}

}

}

public void printMST() {

double totalWeight = 0;

for (int v = 1; v <= numberOfVerticesInMST; v++) {

totalWeight += distTo[v];

System.out.format("%d - %d: %.0f%n", pathTo[v], v, distTo[v]);

}

System.out.format("Total Weight in MST is: %.0f%n", totalWeight);

}

private int getMinWeightIndex(int n) {

int index = -1;

double minWeight = Double.MAX_VALUE;

for (int i = 0; i < n; i++) {

if (!visited[i] && distTo[i] < minWeight) {

index = i;

minWeight = distTo[i];

}

}

return index;

}

}