日期:2014-05-20  浏览次数:20748 次

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