问在有向无环图中寻找最长路径

EN

private static int DAGLongestPath(Graph G) {
int n = G.order();
int[] topOrder = new int[n];
topOrder = topSort2(G);

for (int i = 0; i < topOrder.length; i++) {
    topOrder[i] -= 1;
}   

int[] lengthTo = new int[n];
for (int i = 0; i < n; i++) lengthTo[i] = 0;

for (int i = 0; i < topOrder.length; i++) { //for each vertex v in topOrder(G) do
    ArrayList<Integer> neighbors = new ArrayList<Integer>();
    neighbors = G.neighbors(topOrder[i]);
    int v = topOrder[i];
    for (int j = 0; j < neighbors.size(); j++) {
        int w = neighbors.get(j);
        if(lengthTo[w] <= lengthTo[v] + 1) {
            lengthTo[w] = lengthTo[v] + 1;
        }
    }   
}   

int max = 0;
for (int i = 0; i < n; i++ ) {
    max = Math.max(max, lengthTo[i]);
}
return max;
}

9 // Number of nodes
0: 1 2 
1: 2 3 4
2: 4 8
3: 5 6
4: 6 7 8
5:
6:
7:
8: 7

8 // Number of nodes
0: 2 3
1:
2:
3: 5
4: 5
5: 2
6: 7
7: 4

public static int[] topSort2(Graph G){
    int n = G.order();
    int[] sort = new int[n];

    int[] inDeg = new int[n];
    for (int i=0; i<n; i++) inDeg[i] = G.inDegree(i);

    int cnt = 0;
    boolean progress = true;
    //
    while (progress){
        progress = false;

        for (int v=0; v<n; v++){
            if (inDeg[v] == 0){
                sort[v] = ++cnt;
                progress = true;
                inDeg[v] = -1;

                ArrayList<Integer> nbrs = G.neighbors(v);
                for (int u : nbrs){
                    inDeg[u] = inDeg[u] - 1;
                }
            }
        } // for v

    } // while nodes exist with inDegree == 0.

    return sort;
}

private static int doDFS(Graph G, int v, int[] PreOrder, int[] PostOrder, countPair cnt){
    PreOrder[v] = cnt.inc1();
    int dfsTotal = 0;

    ArrayList<Integer> nbrs = G.neighbors(v);
    for (int i : nbrs) {
        if (PreOrder[i] == 0) {
            int dfsTemp = doDFS(G, i, PreOrder, PostOrder, cnt);
            dfsTotal = Math.max(dfsTotal, dfsTemp);
        }
    }
    PostOrder[v] = cnt.inc2();
    if(nbrs.size() > 0 ) {
        dfsTotal++;
    }
    return dfsTotal;
}

public static int DFS(Graph G, int v, int[] PreOrder, int[] PostOrder){
    int n = G.order();
    int total = 0;
    for (int i=0; i<n; i++) PreOrder[i] = PostOrder[i] = 0;

    countPair cnt = new countPair();
    total = doDFS(G, v, PreOrder, PostOrder, cnt);

    return total;
}

private static class countPair {       // private counters for DFS search
    int cnt1, cnt2;
    int inc1() { return ++cnt1; }
    int inc2() { return ++cnt2; }
}