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

Question

我需要为一组有向无环图找到从节点 0 开始的最长路径。我正在使用 Longest Path Problem algorithm来自维基百科。我的算法适用于大多数图表，但对于其他图表，它没有给出正确的结果。算法是:

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

我得到答案 5，这是正确的。但是，如果我通过图表:

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

然后我得到 2，而正确答案应该是 3。

我使用的 TopSort2 算法是:

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

DFS 算法是:

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

Answer 1

我认为问题出在您的 topSort2() 函数

在函数返回的int[]排序中，索引表示顶点，内容表示顺序。即如果你有 sort[1] = 2，你的意思是顶点 1 是第二个顶点

但是当你使用它的时候，你是以内容为顶点的。也就是说，您将 topOrder[i] 作为顶点，而实际上 i 应该是顶点