如何使函数执行深度优先搜索，并在找到给定顶点时停止搜索

Question

嗨，我是python的新手，我正在为我们在活动中所做的事情而挣扎。我不太明白如何完成这段代码，这样它就可以执行深度优先搜索，当它找到给定的顶点时就会停止。

graph = {'0': ['1', '2'],
'1': ['0', '3', '4'],
'2': ['0', '4'],
'3': ['1', '4'],
'4': ['1', '2', '3', '5'],
'5': ['4', '6'],
'6': ['5']}

def dfs(visited, graph, vertex):
print (vertex)
visited.append(vertex)
for neighbour in graph[vertex]:
if neighbour not in visited:
dfs(visited, graph, neighbour)

# implement this function
def dfs_stop(visited, graph, vertex, target):
pass
dfs([], graph, '0')
print
dfs_stop([], graph, '0', '4')

Answer 1

在对其邻居调用DFS之前，您只需要添加一个检查源节点是否等于目标节点。

def dfs_stop(visited, graph, vertex, target):
print (vertex)
visited.append(vertex)
if (vertex == target):        # to break/stop the function
return
for neighbour in graph[vertex]:
if neighbour not in visited:
dfs_stop(visited, graph, neighbour)