I am making a program to find an mst in a given graph (custom data type). I tested it with a tuple that seemed to work, but when I gave it a different tuple, it says:
Graph:
(1, 2, 1) (1, 3, 0) (2, 4, 0) Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: Index 4 out of bounds for length 4
at Graph$xGraph.edges(Graph.java:18)
at Graph.main(Graph.java:102)
The graph I'm giving it has 4 different vertices so I don't understand the bounds issue.
Here is where I'm setting the bounds of the graph in main:
public static void main(String[] args) {
int v = 4;
xGraph graph = new xGraph(v);
System.out.println("Graph:");
graph.edges(1,2,1);
graph.edges(1,3,0);
graph.edges(2,4,0);
graph.edges(3,4,10);
graph.primMST();
}
And here is the rest of the code:
public class Graph{
static class xGraph{
public int v;
public int m[][];
public xGraph(int vert) {
this.v = vert;
m = new int[vert][vert];
}
public void edges(int start, int end, int weight) {
System.out.print("(" + start + ", " + end + ", " + weight + ") ");
m[start][end]=weight;
m[end][start] = weight;
}
int min(boolean [] mst, int [] weights){
int minweights = Integer.MAX_VALUE;
int vert = -1;
for (int i = 0; i <v ; i++) {
if(mst[i]==false && minweights>weights[i]){
minweights = weights[i];
vert = i;
}
}
return vert;
}
public class minSpanTree{
int parent;
int weight;
}
public void primMST(){
boolean[] mst = new boolean[v];
minSpanTree[] minSpanTree = new minSpanTree[v];
int [] weights = new int[v];
for (int i = 0; i <v ; i++) {
weights[i] = Integer.MAX_VALUE;
minSpanTree[i] = new minSpanTree();
}
weights[0] = 0;
minSpanTree[0] = new minSpanTree();
minSpanTree[0].parent = -1;
for (int i = 0; i <v ; i++) {
int vert = min(mst, weights);
mst[vert] = true;
for (int j = 0; j <v ; j++) {
if(m[vert][j]>0){
if(mst[j]==false && m[vert][j]<weights[j]){
weights[j] = m[vert][j];
minSpanTree[j].parent = vert;
minSpanTree[j].weight = weights[j];
}
}
}
}
printMST(minSpanTree);
}
public void printMST(minSpanTree[] minSpanTree){
int total_min_weight = 0;
System.out.println();
System.out.println("Minimum Spanning Tree: ");
for (int i = 1; i <v ; i++) {
System.out.println("Edge: " + i + " - " + minSpanTree[i].parent +
" weights: " + minSpanTree[i].weight);
total_min_weight += minSpanTree[i].weight;
}
System.out.println("Total minimum weights: " + total_min_weight);
}
}
public static void main(String[] args) {
int v = 4;
xGraph graph = new xGraph(v);
System.out.println("Graph:");
graph.edges(1,2,1);
graph.edges(1,3,0);
graph.edges(2,4,0);
graph.edges(3,4,10);
graph.primMST();
}
}
edit For more information. The program runs with a six vertices graph.
public static void main(String[] args) {
int v = 6;
xGraph graph = new xGraph(v);
System.out.println("Graph:");
graph.edges(0, 1, 2);
graph.edges(0, 2, 4);
graph.edges(1, 2, 2);
graph.edges(1, 3, 1);
graph.edges(2, 3, 6);
graph.edges(3, 4, 7);
graph.edges(4, 5, 3);
graph.primMST();
}
I'm just confused because how can it work with variables that seem equal to one another in purpose?
