DFS在向下遍历时不会命中每个节点

Question

我正在尝试计算有向无环图中最长的节点链。

我正在尝试做的事情如下：

for (Node n: nodes){
    max[n.index] = depth-first-search(n);
}

public static int depth-first-search(Node n){
    for (Node neighbor:n.Neighbors){
        return 1 + depth-first-search(neighbor);
    }
    return 0; //if no neighbors, return 0
}

因此，我们测试一些输入：

Vertex -> Neighbors
Node 1 -> 3
Node 2 -> 0
Node 3 -> 2
Node 4 -> 1, 2, 7
Node 5 -> 3, 1
Node 6 -> 4
Node 7 -> 0

现在我们用每个顶点的最长邻居链填充一个数组，所以如果我们手动完成，我们会得到以下结果：

Node 1 = Length of 2 (3, 2)
Node 2 = Length of 0
Node 3 = Length of 1 (2)
Node 4 = Length of 4 (3, 2, 1, 7)
Node 5 = Length of 3 (2, 3, 1)
Node 6 = Length of 5 ( 2, 3, 1, 4, 7) <-Longest 
Node 7 = Length of 0

如果我在我的程序中运行它，数组看起来像这样：

Node 1 = Length of 2 <- Correct
Node 2 = Length of 0 <- Correct
Node 3 = Length of 1 <- Correct
Node 4 = Length of 3 <- Off by 1
Node 5 = Length of 2 <- Off by 1
Node 6 = Length of 4 <- Off by 1
Node 7 = Length of 0 <- Correct

我继续跟踪Node 6的算法，注意到它忽略了Node 7。跟踪如下：

dfs(6)
   return 1+dfs(4)
      return 1+ dfs(1)
        return 1+ dfs(3)
         return 1+ dfs(2)
          return 0 

正如我们所看到的，它从来没有命中节点7，我也不清楚为什么。我试着在depth-first-search()中将行"return 0“改为"return 1”，它确实将长度减少了1，但它将所有以前正确的长度都改成了1。如果有人能提供一些帮助，我将非常感激。

Answer 1

由于return语句，您只能看到一个邻居。你需要检查所有的邻居。

public static int depth-first-search(Node n){
    int max = 0; //if no neighbors, return 0
    for (Node neighbor:n.Neighbors){
        max = Math.max(max, 1 + depth-first-search(neighbor));
    }
    return max;
}

更新：

我不认为你的预期答案是正确的：

Node 1 = Length of 2 (3, 2)
Node 2 = Length of 0
Node 3 = Length of 1 (2)
Node 4 = Length of 4 (3, 2, 1, 7)
Node 5 = Length of 3 (2, 3, 1)
Node 6 = Length of 5 ( 2, 3, 1, 4, 7) <-Longest 
Node 7 = Length of 0

正确的解决方案应该是

Node 1 = Length of 2 (3 -> 2)
Node 2 = Length of 0 ()
Node 3 = Length of 1 (2)
Node 4 = Length of 3 (1 -> 3 -> 2)
Node 5 = Length of 3 (1 -> 3 -> 2)
Node 6 = Length of 4 (4 -> 1 -> 3 -> 2) <-Longest 
Node 7 = Length of 0 ()