求助！如何将如下的递归代码变成迭代？

Question

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，所以只能写迭代。谢谢了！

Answer 1

其实这是个很简单的迭代吧  怎么搞这么复杂哦
看你代码有点没明白根据你文字描述的写了写一个 public static int longestPath(int start,int[] topo){  
int i = 0 ;
for (int j = 0; j < topo.length; j++) {

int y = Math.abs(topo[j] - start) ;
if(i<y){
i = y ;
}
}
return i  ;
}

Answer 2

回楼上：
longestPath是求某个顶点开始的最长路径，数组topo是已经拓扑排序好的节点号码，譬如说
1-->3-->2-->0的话topo就是{1,3,2,0}的数组，然后loop的时候就逐个逐个看v（按照拓扑排序的每个节点）与start（开始的节点）比是不是有向边，是的话就递归求从v开始的最大路径，然后跟longest比较，比longest大就取temp为longest第二个是求某个点到某个点有多少个不同路径。如果两个节点相同，那么路径数就是1，否则就从拓扑排序好的数组从后开始往前数，如果与某个点有边的话就加上那个边，直到到达起点。两个都是用动态规划的思路做的。只是用了递归，很慢啊我人比较笨，不会转化成迭代

Answer 3

把isArc(start,v)函数的代码一起贴出来吧 ， 真的不很很明白你怎么做的，看代码才知道

Answer 4

isArc(start,v)是判断从start到v有没有有向边，没有什么深奥的东西,这是全部的源代码class GraphAdjLists
{
    //  Internal Representation and Constructors
    //
    protected ArrayList<ArrayList<Integer>> adj;
int[] seenTimes;
int[] doneTimes;
int[] state;
Stack<Integer> S = new Stack<Integer>();
int components;
int time;
    public GraphAdjLists()
    {
        adj = new ArrayList<ArrayList<Integer>>();
    }    public GraphAdjLists(Scanner scanner){       
        try{
String line = buffer.nextLine().trim();
String[] tokens = line.split("\\s+"); if (tokens.length != 1){
throw new Error("bad format: number of vertices");
} adj = new ArrayList<ArrayList<Integer>>();
int n = Integer.parseInt(tokens[0]); for (int u = 0; u < n; u++){
ArrayList<Integer> current = new ArrayList<Integer>();
line = buffer.nextLine().trim();
int limit = 0;
if (!line.equals(""))
{
tokens = line.split("\\s+");
limit = tokens.length;
}
for (int i = 0; i < limit; i++)
{
current.add(Integer.parseInt(tokens[i]));
}
adj.add(current);
}
seenTimes = new int[order()];
doneTimes = new int[order()];
state = new int[order()]; 
}catch(Exception ex){

}
}
    //  Mutator Methods
    //
    public void addVertices(int n)
    {
        assert(0 <= n);
        if ( n > 0 )
        {
            for (int i = 0; i < n; i++)
            {
                adj.add(new ArrayList<Integer>());
            }
        }
    }    public void removeVertex(int i)
    {
        assert(0 <= i && i < order());
        adj.remove(i);
        Integer I = new Integer(i);
        for (int u = 0; u < order(); u++)
        {
            ArrayList<Integer> current = adj.get(u);
            current.remove(I); // remove i from adj lists
            for (Integer num: current)
            {
                if (num > i)  // relabel larger indexed nodes
                {
                    int index = current.indexOf(num);
                    current.set(index, num-1);
                }
            }
        }
    }    public void addArc(int i, int j)
    {
        assert(0 <= i && i < order());
        assert(0 <= j && j < order());
        if (isArc(i,j)) return;
        (adj.get(i)).add(j);
    }    public void removeArc(int i, int j)
    {
        assert(0 <= i && i < order());
        assert(0 <= j && j < order());
        if (!isArc(i,j)) return;
        (adj.get(i)).remove(new Integer(j));
    }    public void addEdge(int i, int j)
    {
        assert(0 <= i && i < order());
        assert(0 <= j && j < order());
        if (!isArc(i,j)) (adj.get(i)).add(j);
        if (!isArc(j,i)) (adj.get(j)).add(i);
    }    public void removeEdge(int i, int j)
    {
        assert(0 <= i && i < order());
        assert(0 <= j && j < order());
        if (isArc(i,j)) (adj.get(i)).remove(new Integer(j));
        if (isArc(j,i)) (adj.get(j)).remove(new Integer(i));
    }
    //  Access Methods
    //
    public boolean isArc(int i, int j)
    {
        assert(0 <= i && i < order());
        assert(0 <= j && j < order());
        return (adj.get(i)).contains(new Integer(j));
    }    public boolean isEdge(int i, int j)
    {
        assert(0 <= i && i < order());
        assert(0 <= j && j < order());
        return isArc(i,j) && isArc(j,i);
    }    public int inDegree(int i)
    {
        assert(0 <= i && i < order());
        int sz = 0;
        for (int j = 0; j < order(); j++)
        {
            if (isArc(j,i))  sz++; 
        }
        return sz;
    }    public int degree(int i)
    {
        assert(0 <= i && i < order());
        return (adj.get(i)).size();
    }    public ArrayList<Integer> neighbors(int i)
    {
        assert(0 <= i && i < order());
        ArrayList<Integer> nei = new ArrayList<Integer>();
        for (Integer vert : adj.get(i))
        {
            nei.add(vert);
        }
        return nei;
        //return (ArrayList<Integer>)(adj.get(i)).clone(); <-- -Xlint doesn't like this. [Unchecked cast]
    }    public int order()
    {
        return adj.size();
    }    public int size()  // Number of arcs (counts edges twice).
    {
        int sz = 0;
        for (int i=0; i<order(); i++)
        {
            sz += (adj.get(i)).size();
        }
        return sz;
    }    // default output readable by constructor
    //
    public String toString()
    {
        return toStringAdjLists();
    }
    public String toStringAdjLists()
    {
        StringBuffer o = new StringBuffer();
        o.append(order()+"\n");        for (int i = 0; i < order(); i++)
        {
            ArrayList<Integer> nei = neighbors(i);
            for (int j : nei)
            {
                o.append(j + " ");
            }
            o.append("\n");
        }
        return o.toString();
    }

public void DFS(){
for (int i = 0; i < order(); i++){
state[i] = 0;//Vertex state = white
}
for(int s = 0; s < order(); s++){
if(state[s]==0){
dfsvisit(s);
}
}
int[] topo = topoSort(doneTimes);
System.out.println(getNumOfPaths(order()-1,topo));
}
public void dfsvisit(int s){
state[s] = 1;//Gray
seenTimes[s] = time;
//System.out.format("%d is seen, time: %d\n",s,time);
time++;
S.push(s);
while(!S.empty()){
int u = S.peek();
int v = hasNext(u);
if(v!=-1){
state[v] = 1;
seenTimes[v] = time;
//System.out.format("%d is seen, time: %d\n",v,time);
time++;
S.push(v);
}else{
S.pop();
state[u] = 2;//Black
doneTimes[u] = time;
//System.out.format("%d is done, time: %d\n",u,time);
time++;
}
}
}
public int hasNext(int u){
ArrayList<Integer> nbrs = neighbors(u);
for(int v : nbrs){
if(state[v]==0){
return v;
}
}
return -1;
}

public int[] topoSort(int[] doneTimes){
int[] copy = doneTimes.clone();
int[] topo = new int[doneTimes.length];
Arrays.sort(doneTimes);
int k = 0;
for(int i = doneTimes.length-1;i>-1;i--){
for(int j = 0;j<copy.length;j++){
if(copy[j]==doneTimes[i]){
topo[k] = j;
k++;
}
}
}
return topo;
}

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;
}（不要吐槽我命名啊缩进啊很混乱）
这是一个用邻接表储存的有向无环图（DAG）

Answer 5

虽然上面代码里有个用DFS完成时间拓扑排序的方法但是我已经不用了，太慢了，无视吧，只是可以假设已经得到一个拓扑排序好的数组topo就是了（不过跟DFS完成时间排列的不同）

Answer 6

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];
}