Why Depth-First-Search code is not working in some cases?-CodePudding

This is the graph

So, I try DFS code like this

# Using a Python dictionary to act as an adjacency list
graph = {
'A' : ['B','C'],
'B' : ['D', 'E'],
'C' : ['G', 'H'],
'D' : [],
'E' : ['F'],
'G' : [],
'H' : ['I'],
'F' : [],
'I' : ['J'],
'J' : []
}

visited = [] # Set to keep track of visited nodes of graph.
visited_new = []

def dfs(visited, graph, node, goal): #function for dfs
    if node not in visited:
#         print (visited)
        visited.append(node)
        for neighbour in graph[node]:
#             print(visited)
            if neighbour not in visited:
                dfs(visited, graph, neighbour, goal)
                
            if neighbour == goal:
                idx_goal = visited.index(goal)
                return visited[:idx_goal 1]
        
            

# Driver Code
print("Following is the Depth-First Search")
print(dfs(visited, graph, 'A', 'C'))

The output like this :

Following is the Depth-First Search
['A', 'B', 'D', 'E', 'F', 'C']

But when I change parameter 'A' to 'F' like this dfs(visited, graph, 'A', 'C') and the output is :

Following is the Depth-First Search
None

I expect ['A', 'B', 'D', 'E', 'F']

Not only 'A' to 'F', the output code is working only 'A' to 'B' and 'A' to 'C'

How I can solve this problem?

CodePudding user response：

With the way your code is written above, your function will only return a result if the original goal is in the neighbor list of the original node ('C' is in A's neighbor list so it hits if neighbour == goal: ... return. However, for the recursive calls you are not checking to see the result of dfs (which is not capable of breaking out of the parent function which called it).

Here is a runnable working example!

#!/usr/bin/env python
# Using a Python dictionary to act as an adjacency list
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['G', 'H'],
    'D': [],
    'E': ['F'],
    'G': [],
    'H': ['I'],
    'F': [],
    'I': ['J'],
    'J': []
}

visited = []  # Set to keep track of visited nodes of graph.
visited_new = []


def dfs(visited, graph, node, goal):  # function for dfs
    if node not in visited:
        visited.append(node)
        for neighbour in graph[node]:
            if neighbour not in visited:
                r = dfs(visited, graph, neighbour, goal)
                # dfs will only return a result if it has found a path, otherwise the return will be None
                if r is not None:
                    # if a result is found, return the result now, no need to
                    # visit remaining nodes
                    return r

            if neighbour == goal:
                idx_goal = visited.index(goal)
                return visited[:idx_goal   1]


# Driver Code
print("Following is the Depth-First Search")
print(dfs(visited, graph, 'A', 'F'))

<script src="https://modularizer.github.io/pyprez/pyprez.min.js"></script>

CodePudding user response：

The problem is that you are not saving the return from the recursive call that reaches the goal, precisely here:

            if neighbour not in visited:
                dfs(visited, graph, neighbour, goal)

Your function does not return anything (hence the None) when you are at the recursive call that doesn't reach the goal in one step.

You can fix that by either having a variable that keeps track of the not-None return value, or by keeping a global variable that you update in the recursive calls, without having to store return values.

CodePudding user response：

Usually with DFS the goal isn't to return every node that you visited to find a direct path. The result should simply be the direct path to the target.

For example:

graph = {'A' : ['B','C'],'B' : ['D', 'E'],'C' : ['G', 'H'], 'D' : [],
         'E' : ['F'],'G' : [],'H' : ['I'],'F' : [],'I' : ['J'],'J' : []}

def dfs(visited, graph, node, goal):
    if node == goal:            # base case
        return [node]           # return node list
    visited.append(node)
    for neighbor in graph[node]:
        if neighbor not in visited:    # check neighbors
            result = dfs(visited, graph, neighbor, goal)
            if result:                  # if result is returned then 
                return [node]   result  # we have found the target and append the node to the list
    return []                          

print("Following is the Depth-First Search")
print(dfs([], graph, 'A', 'F'))
print(dfs([], graph, 'A', 'C'))
print(dfs([], graph, 'A', 'H'))
print(dfs([], graph, 'A', 'J'))
print(dfs([], graph, 'A', 'G'))

Output

Following is the Depth-First Search
['A', 'B', 'E', 'F']
['A', 'C']
['A', 'C', 'H']
['A', 'C', 'H', 'I', 'J']
['A', 'C', 'G']

If you actually wanted a list of nodes that you visited to find the target you can still use the same algorithm you would just want to create an empty list before each call for the visited parameter and print that out instead. For example:

print("Following is the Depth-First Search")
for char in ["F", "C", "H", "J", "G"]:
    visited = []
    print(f"(A,{char}) Direct Path = ", dfs(visited, graph, 'A', char))
    print(f"(A,{char}) Nodes Visited = ", visited, "\n")

output:

Following is the Depth-First Search
(A,F) Direct Path =  ['A', 'B', 'E', 'F']
(A,F) Nodes Visited =  ['A', 'B', 'D', 'E']

(A,C) Direct Path =  ['A', 'C']
(A,C) Nodes Visited =  ['A', 'B', 'D', 'E', 'F']

(A,H) Direct Path =  ['A', 'C', 'H']
(A,H) Nodes Visited =  ['A', 'B', 'D', 'E', 'F', 'C', 'G']

(A,J) Direct Path =  ['A', 'C', 'H', 'I', 'J']
(A,J) Nodes Visited =  ['A', 'B', 'D', 'E', 'F', 'C', 'G', 'H', 'I']

(A,G) Direct Path =  ['A', 'C', 'G']
(A,G) Nodes Visited =  ['A', 'B', 'D', 'E', 'F', 'C']