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