求助!如何将如下的递归代码变成迭代?
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];
}