找到目标顶点和 Return 路径时退出 DFS 递归

Question

我做了一个递归 DFS 算法，它可以 return 找到目标时的路径。请注意，我正在利用递归，并尝试在路径保存中使用尽可能少的内存。找到目标后，保证 path 将包含正确的路径。但是 DFS 必须完全停止，否则我无法 return 由于 pop() 之后的正确列表。临时解决方案是全局列表result。有没有办法：

找到目标后停止递归？
Return path 列表恰好在指定点 ?

result = []

def dfs(graph, vertex, visited, path):

    global result
    if vertex not in visited:
        visited.add(vertex)
        if isTarget(vertex):
            print("Solution found ! " + str(path))
            result = path.copy() # recursion must stop here and return path at this state
        for neighbor in graph.getSuccessors(vertex):
            path.append(neighbor[1]) #neighbor[1] is direction 
            print("Visiting node" + str(neighbor[0]))
            dfs(graph, neighbor[0], visited, path)
            path.pop()

Answer 1

我建议将搜索逻辑与遍历逻辑分开。这允许您以通用方式编写 dfs 并重用它来遍历图形以进行任何与图形相关的操作 -

def dfs(graph, vertex, path = tuple(), visited = set()):
  if vertex in visited: return
  yield (vertex, path)
  for [v,dir] in graph.getSucessors(vertex):
    yield from dfs(graph, v, (*path, dir), {*visited, v})

现在 find 只是我们可以围绕 dfs -

编写的众多函数之一

def find(graph, start, target):
  for (v, path) in dfs(graph, start):
    if v == target:
      return (v, path)
  return (None, None)

dfs 是惰性的，因此迭代将在 find returns 时停止。这是您如何使用它的示例 -

(vertex, path) = find(graph, startVertex, targetVertex)
if not vertex:
  print("target not found")
else:
  print(f"found {vertex} at path {path}")

这种方法的一个优点是不仅能找到第一个目标，还能找到所有个目标-

def find_all(graph, start, target):
  return list((v, path) for (v, path) in dfs(graph, start) if v == target)

如果您分享 graph.getSuccessors，我相信我们也可以对其进行优化。如果你把它写得像 dfs 那样懒惰，两个生成器都可以从提前退出行为中受益。

Answer 2

根据我的想法，dfs() 可以 return 一个列表，这将允许我们 continue/break 递归。类似于：

result = []

def dfs(graph, vertex, visited, path):

    if vertex not in visited:
        visited.add(vertex)
        if isTarget(vertex):
            print("Solution found ! " + str(path))
            return path # recursion stops here and returns path at this state
        for neighbor in graph.getSuccessors(vertex):
            path.append(neighbor[1]) #neighbor[1] is direction 
            print("Visiting node" + str(neighbor[0]))
            temp_path = dfs(graph, neighbor[0], visited, path)
            if temp_path:
                return temp_path # break recursion since path found
            path.pop()
    return [] # if no path/target node found

result = dfs()

找到目标顶点和 Return 路径时退出 DFS 递归

Exit DFS Recursion When Target Vertex Is Found And Return Path

python

algorithm

recursion

search

depth-first-search