Skip to content
Advertisement

How I can stop depth first search at specific node

Here Is my python code:

# Using a Python dictionary to act as an adjacency list
graph = {
  'A' : ['B','C','D'],
  'B' : ['E', 'F'],
  'C' : ['G'],
  'E' : [],
  'F' : [],
  'G' : ['K','H'],
  'K' : [],
  'H' : [],
  'D' : [],
 
 
}
 
visited = set() # Set to keep track of visited nodes of graph.
 
def dfs(visited, graph, node):  #function for dfs 
    if node not in visited:
        print (node)
        visited.add(node)
        for neighbour in graph[node]:
            dfs(visited, graph, neighbour)
            break
            
 
# Driver Code
print("Following is the Depth-First Search")
dfs(visited, graph, 'A')

its about depth first search algorithm and when I compile it without break statement the result would be: A B E F C G K H D

and when i put break statement the result would be: A B E and my question is how i can here stop this algorithm at specific node like F so the result would be like

A B E F

I have tried to put break after line 23 but it just give me this result A B E but I want F to be included in it

Advertisement

Answer

In order to stop the loop, we would want to return something if the node, for which you are searching for, is found:

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

}

visited = set()  # Set to keep track of visited nodes of graph.


def dfs(visited, graph, node, stop_at):  # function for dfs
    if node not in visited:
        print(node)

        # We check if the current node is the one for which we are looking for
        if node == stop_at:
            return True

        visited.add(node)
        for neighbour in graph[node]:
            # If we found the node, we break out from the loop
            if dfs(visited, graph, neighbour, stop_at):
                return True
        # If we did not find the node we were looking for, we return False
        return False


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

In case of dfs(visited, graph, 'A', 'F'), it should print:

A
B
E
F
User contributions licensed under: CC BY-SA
4 People found this is helpful
Advertisement