使用DFS递归查找特定路径

Question

我试图使用DFS解决一个图形问题，但遇到了一堵墙。这是我在Python3中的实现。unvisited是一个整数数组，start和end是unvisited中的整数，path是一个空数组，在DFS运行时填充，edges是一个边字典。

def traverse(unvisited, start, end, path, edges):

copy_unvisited = unvisited.copy()
copy_path = path.copy()
current = start
copy_unvisited.remove(current)
copy_path.append(current)
if current == end and len(copy_unvisited)==0:
    #print is just for me to check my answers
    print(copy_path)
    return copy_path
for i in edges[current]:
    if i in copy_unvisited:
        return traverse(copy_unvisited, i, end, copy_path, edges)

目标是找到一条从开始到结束访问unvisted中所有int的路径。因此，我遇到了递归的问题（我认为），因为在路径错误的情况下，我不想返回任何东西；相反，我希望DFS继续。按照现在编写代码的方式，即使打印出正确的解决方案（因为我的打印语句），我也会得到“无”返回。我如何解决这个问题？

提前感谢！

编辑：如果未访问=[1,3,4,5]，开始=4，结束=5，边缘={1: (4,5), 3: (1), 4: (1,3,5), 5: (1,4)}，

遍历（unvisited，4，5，[]，edges）应该返回[4,3,1,5]，但是我没有得到任何结果。如果遵循了错误的路径，traverse没有返回类型，这就是为什么我认为我没有得到返回类型。它最终找到了正确的路径并打印出来。

我通过引入一个新参数sol找到了一个解决方案，当到达正确的路径时，我将copy_path的每个条目复制到sol中。然后，在递归调用结束后，我返回sol。我还删除了递归调用的return语句。

def traverse(unvisited, start, end, path, edges,sol):
copy_unvisited = unvisited.copy()
copy_path = path.copy()
current = start
copy_unvisited.remove(current)
copy_path.append(current)
if current == end and len(copy_unvisited)==0:
    for i in copy_path:
        sol.append(i)
for i in edges[current]:
    if i in copy_unvisited:
        traverse(copy_unvisited, i, end, copy_path, edges,sol)
return sol

感觉有点不优雅，所以我愿意用更好的方法来解决这个问题！

Answer 1

首先，根据您给出的输入，输出应该是[4 1 5]，因为链接到顶点4的第一条边是1，并且在第一次执行DPS 1时，仍然在未访问列表中。

原始代码的主要问题是以下两个指令

len(copy_unvisited)==0: 

在第一个if和

if i in copy_unvisited:

在最后。

基本上你有：

First call of the function: 
node 4, unvisited (uv): [1,3,4,5], path=[]
At the for: 4 uv: [1,3,5] edges: (1, 3, 5)
So i=1, i is in uv, then:
Second call of the function:
node 1, uv: [1,3,5], path=[4]
At the for: 1 uv: [3,5] edges: (4,5)
So i=4, but 4 is not in uv,
So i=5, 5 is in uv, then:
Third call of the function *OBS1*
node 5, uv: [3,5], path=[4,1]
it will not enter in the first if, because len(uv) is not equals 0.
At the for: 5 uv: [3] edges: (1,4)
So i=1, but 1 is not in uv
So i=4, but 4 is not in uv

函数结束，不调用自身，也不返回值。

我非常确定DPS应该在您进入想要的节点时结束，或者在您没有更多节点可访问时结束。在第一种情况下，它应该返回找到的路径，如果没有，则表示结束节点没有从开始节点到结束节点的路径（在断开连接的图中）。

我试图修改您的实现，但我发现很难处理这个“未访问”变量，也很难用这种方式更新路径。我不认为你在概念上是错误的，无论是在DFS应该如何工作的概述中，还是在如何更新循环中，但我无法让它以这种方式工作，所以我修改了算法，以便它在取消堆栈函数时更新路径，而不是在调用函数时更新路径。

def traverse(start,end,edges,visited=[],path = []):
    if start == end:
        path.append(start)
        return path
    if start not in visited:
       visited.append(start)
       if start not in edges:
           return path

       for i in edges[start]:

           path = traverse(i,end,edges,visited,path )
           if len(path)>0:
               break

    if len(path)>0 and start not in path:
        path.append(start)
    return path

这将返回反向写入的路径，如果您希望按照正常顺序，只需获取函数的最终结果，这将是一个列表并应用。对其使用reverse（）方法。

上面的实现是对我在这里找到的实现的轻微修改：https://likegeeks.com/depth-first-search-in-python/我只是添加了在两个特定点之间查找路径的部分。

你的“sol”解决方案之所以有效，部分原因是，当DFS进入第三个调用并离开for而不再次调用函数时，它至少可以返回一个空列表，然后第三个调用离开堆栈，算法继续到第二个函数调用的下一个i，即3。此实现的问题是DFS将在返回到目标的路径之前读取所有节点。