在有向非循環圖中尋找最長路徑

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應該是頂點