CODEWITHSUNDEEP
pythonalgorithmrecursiondepth-first-search
user3088454
user3088454

Reputation:

Depth first search: return values

I was reading about depth first search (here) and was wondering why we don't return the value of the recursive call. This might sound strange, so here's the code with the line in question commented:

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

My question: would replacing:

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

with

return depthFirst(adjNode, soughtValue, visitedNodes):

cut the search short by evaluating to False prematurely? The lines in question seems to be saying follow the current adjNode and see if it leads to a solution; if it does, we'll get a series of True statements returned all the way to the beginning of the search (our current adjNode) from the leaf; this happens all the way to the root (the start of our search and the first recursive call). Only then we can say we've found a valid path and return 'True'.

It seems as though the first return statement triggers the chain of 'True' statements and we leave the search inside the loop. Am I correct? There's a lot going on and any further explanation would be greatly appreciated.

Upvotes: 3

Views: 3284

Answers (3)

Khaled Alnaami
Khaled Alnaami

Reputation: 51

Suppose we have the following graph:

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

Where soughtValue is node 9. Starting from node 1 as source:

   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

Upvotes: 4

mhlester
mhlester

Reputation: 23231

We can't return any value, because if it's False, the for loop breaks and never finds the True that may be later..

Example:

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

Upvotes: 0

Simeon Visser
Simeon Visser

Reputation: 122376

Yes, the search needs to continue if depthFirst(adjNode, soughtValue, visitedNodes) returns False. Only when you've found the sought value in that part of the graph then you can return True for your search.

If you were to replace that with return depthFirst(adjNode, soughtValue, visitedNodes) then you'll only search for the value in that part of the graph (starting from that adjacent node) but you won't continue your search in case the value isn't found there.

Upvotes: 0

Related Questions