在有向非循环图中寻找最长路径

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中，索引表示顶点，内容表示顺序。即如果有sort[1] = 2，则表示顶点1是第二个顶点

但是，当您使用它时，会将内容作为顶点。即你拿topOrder[i]作为顶点，而实际上i应该是顶点