我已经编写了一个代码,用于从硬编码到 main 中的图形中获取最大流量。我按照指示进行操作,但我不断收到此错误,我不知道为什么。我试过改变很多部分和调试,但我想不通。这是错误:
Exception in thread "main" java.lang.NullPointerException
at lib280.graph.FF.dft(FF.java:78)
at lib280.graph.FF.isRes(FF.java:67)
at lib280.graph.FF.findMax(FF.java:40)
at lib280.graph.FF.main(FF.java:117)
这是我的代码:
package lib280.graph;
public class FF {
public boolean[] visited;
double parent[];
public int maxflow;
public int findMax(double G[][], int s, int t){
maxflow = 0;
int a = G.length; //length of rows
int b = G[0].length; // length of columns
int v = a*b; // vertices
int i, j;
double c;
double[][] residual = new double[a][b]; //the initializion for the residuals
//Create residual of G
for (i=0;i<a;i++){
for (j=0; j<b;j++){
residual[i][j] = G[i][j];
}
}
//while the path from s to t is residual, find max flow
while (isRes(residual, s, t, parent)){
int path = Integer.MAX_VALUE; //(LINE 40)
for (double h=t; h<s; h=parent[(int)h]){
c = parent[(int)h];
path = Math.min(path, (int)residual[(int)c][(int)h]);
}
for (double h=t; h<s; h=parent[(int)h]){
c = parent[(int)h];
residual[(int)c][(int)h] -= path; //residual for the edge
residual[(int)h][(int)c] += path; //residual for the reverse edge
}
maxflow = maxflow+path; //update max
}
return maxflow;
}
public boolean isRes(double G[][], int s, int t, double parent[]){
dft(G, s);
return (visited[t]==true); //(Line 67)
}
public void dft(double G[][], int s){
for (int i=0;i<G.length;i++){ // initializing every vertex not visited
visited[i] = false; // (Line 78)
}
dftHelper(G, s);
}
public void dftHelper(double G[][], int s){
visited[s] = true;
for (int i=0; i<G.length; i++){
if (visited[i]==false && G[s][i]>0){ // for each node adjacent to s and if it is not reached
dftHelper(G, i);
}
}
}
这是 main 的精简版:
public static void main(String args[]) throws Exception {
FF a = new FF();
double G[][] = hardcoded graph
int x = a.findMax(G, 0, 5);
System.out.println("Max flow" + x); //(Line 117)
System.out.println("Final Residual Capacities: ");
}
}