- Java code
public int longestPath(int start,int[] topo){ int longest = 0; for(int v:topo){ if(isArc(start,v)){ int temp = longestPath(v,topo)+1; if(longest < temp){ longest = temp; } } } return longest; } public long getNumOfPaths(int v,int[] topo){ long numOfPaths = 0; if(v==0){ numOfPaths = 1; }else{ for(int i:topo){ if(isArc(i,v)){ numOfPaths += getNumOfPaths(i,topo); } } } return numOfPaths; }
这是两个图论方法,第一个方法是求出从起点开始的最长距离,第二个是求出从起点到终点(key最大)的路径数,图是有向无环图
请问该怎么把这两个方法写成迭代的形式呢?因为节点数有几千个,会有stackoverflowerror,所以只能写迭代。谢谢了!
------解决方案--------------------
public int longestPath3(int start,int[] topo,Graph dagRev,int[] dist,int[] turn){
int temp;
for(int v : topo){
temp = 0;
if(turn[v]<=turn[start]||dagRev.neighbors(v).isEmpty()){
dist[v]=0;
}else{
for(int u:dagRev.neighbors(v)){
if(dist[u]==0&&u!=start){
temp = 0;
}else{
temp = dist[u] + 1;
}
if(dist[v]<temp){
dist[v]=temp;
}
}
}
}
int longest = getMax(dist);
return longest;
}
public int getMax(int[] dist){
int max = dist[0];
for(int i : dist){
if(max<i){
max = i;
}
}
return max;
}
public long getNumsOfPath3(int start,int[] topo, Graph dagRev, long[] pathsNums, int[] turn){
for(long i:pathsNums){
i = 0;
}
for(int v:topo){
if(turn[v]<turn[start]){
pathsNums[v]=0;
}else if(v==start){
pathsNums[v] = 1;
}else{
for(int u:dagRev.neighbors(v)){
pathsNums[v]+=pathsNums[u];
}
}
}
return pathsNums[order()-1];
}