深度优先搜索：返回值

Question

我正在阅读深度优先搜索（here），并想知道为什么我们不返回递归调用的值。这可能听起来很奇怪，所以这里的代码有问题：

def depthFirst(node, soughtValue, visitedNodes):
    if node.value == soughtValue:
        return True

    visitedNodes.add(node)
    for adjNode in node.adjacentNodes:
        if adjNode not in visitedNodes:
            if depthFirst(adjNode, soughtValue, visitedNodes): # why this?
              return True

    return False

我的问题：将取代：

if depthFirst(adjNode, soughtValue, visitedNodes):
    return True

同

return depthFirst(adjNode, soughtValue, visitedNodes):

通过过早评估False来缩短搜索范围？有问题的线似乎是跟随当前的adjNode并看看它是否会导致解决方案;如果确实如此，我们将从叶子中获得一系列True语句一直返回到搜索开头（我们当前的adjNode）;这种情况一直发生在根（搜索的开始和第一次递归调用）。只有这样我们才能说我们找到了一条有效路径并返回'True'。

似乎第一个return语句触发了'True'语句链，我们将搜索留在循环中。我对么？有很多事情发生，任何进一步的解释将不胜感激。

Answer 1

我们不能返回任何值，因为如果它是False，for循环中断并且永远不会找到可能稍后的True ..

例：

def divisible_by_five_A():
    for n in range(100):
        if n and not n % 5:
            return n, 1

divisible_by_five_A()
# O: 5, 1

VS

def divisible_by_five_B():
    for n in range(100):
        return n, (n and not n % 5)

divisible_by_five_B()
# O: 0, 0

Answer 2

假设我们有以下图表：

            1 ——— 2
            |     
            4 ——— 5 ——— 6
            |     |     |     
            7 ——— 8 ——— 9

其中seekValue是节点9.从节点1开始作为源：

   wrong code:
   ===========
   dfs(1,9,…)                          dfs(2,9,…)  
       …                                    …
       // neighbors                        // neighbors          
       return dfs(2,9,…)  <———|            NO return dfs(1,9,…) as 1 has been visited
       return dfs(4,9,…)      |             
                              |             
                              |            so return false
                              |             |
                              |-------------|

   result
   dfs(1,9,…) terminates with a false even without going to dfs(4,9,…)



   correct code:
   ============
   dfs(1,9,…)                  dfs(2,9,…)     
        …                           …
       // neighbors                // neighbors                
       if (dfs(2,9,…)) <———|       NO if dfs(1,9,…) as as 1 has been visited
            return true    |           return true
                           |
       if (dfs(4,9,…))     |    
            return true    |    
                           |             
                           |        so return false
                           |             |
                           |-------------|

   result
   dfs(1,9,…) doesn't terminate and does continue to other neighbors (i.e., dfs(4,9,…)) and so on until we reach the soughtValue 9 and return true

Answer 3

是的，如果depthFirst(adjNode, soughtValue, visitedNodes)返回False，搜索需要继续。只有当您在图表的该部分找到了所需的值时，您才能返回True进行搜索。

如果您要用return depthFirst(adjNode, soughtValue, visitedNodes)替换它，那么您将只搜索图形部分中的值（从该相邻节点开始），但是如果在那里找不到值，则不会继续搜索。