如何在特定节点停止深度优先搜索

Question

这是我的 python 代码：

# 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')

它是关于深度优先搜索算法的，当我在没有 break 语句的情况下编译它时，结果将是：一种乙乙 F C G 钾 H D

当我输入 break 语句时，结果将是：一种乙乙我的问题是如何在 F 之类的特定节点停止此算法，因此结果会像

一个乙乙 F

我试图在第 23 行之后放置 break，但它只给了我这个结果一种乙乙但我希望 F 包含在其中

Answer 1

为了停止循环，如果找到了您正在搜索的节点，我们希望return做一些事情：

# 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')

在 dfs(visited, graph, 'A', 'F') 的情况下，它应该打印：

A
B
E
F

如何在特定节点停止深度优先搜索

How I can stop depth first search at specific node

python

depth-first-search