深度优先搜索：返回值

Question

我在阅读关于深度优先搜索的内容（这里），想知道为什么我们不返回递归调用的值。这可能听起来很奇怪，因此下面是包含问题注释的代码：

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”语句链，并且我们在循环内离开搜索。我正确吗？这里发生了很多事情，任何进一步的说明都将不胜感激。

- user3088454

Answer 1

假设我们有以下图表：

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

在以节点1为源的情况下，寻找值为9的节点。

   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

- Khaled Alnaami

Answer 2

我们无法返回任何值，因为如果它是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

对比

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

divisible_by_five_B()
# O: 0, 0

- mhlester

Answer 3

是的，如果depthFirst(adjNode, soughtValue, visitedNodes)返回False，搜索需要继续。只有当你在图的那一部分找到所需的值时，才能为你的搜索返回True。

如果你用return depthFirst(adjNode, soughtValue, visitedNodes)替换它，那么你只会在图的那一部分（从那个相邻节点开始）搜索该值，但如果在那里没有找到该值，你不会继续搜索。

- Simeon Visser