深度优先图搜索返回目标路径

Question

我这周一直在尝试这个问题，但无论如何都搞不明白。

我知道我需要一个辅助函数，它会递归调用并返回当前的路径（pathSoFar）。但是我就是搞不懂递归是怎么回事。

我现在困惑得连问题到底是什么都说不清，除了递归之外。

谢谢大家的帮助。

编辑：好的，我再解释一下。有一件事让我困惑，就是当一个节点没有邻居时，应该返回什么路径。可能会先返回目标路径，但因为辅助函数还在递归，所以它可能会返回一条死胡同的路径。我想我对回溯这个概念感到困惑。

Answer 1

递归就是把一个大问题拆分成几个小问题来解决。

比如说，你想从节点A找到到节点Z的路径。首先，你看看A的邻居，假设它们是B、C和D。

这样你就有了三个小问题：从B到Z的路径、从C到Z的路径，以及从D到Z的路径。如果你能解决其中任何一个小问题，那你就相当于解决了从A到Z的这个大问题。

所以，你就开始递归。你对B、C和D分别使用你的findPath方法，并给每个方法传一个已经访问过的节点列表，这个列表里包含A（这样可以防止它们回头走）[1]。如果其中任何一个说“我找到了路径”，你就把它返回的路径拿过来，把A放在路径的开头，这样就完成了。

在递归调用的过程中，最终你会到达一个邻居是Z的节点（前提是A和Z之间确实有连接）。一旦发生这种情况，你就解决了问题：返回这个路径。如果你到达了一个死胡同，所有邻居都已经访问过了，那就返回一些代码，告诉调用者这是个死胡同，他们不应该用这个节点来尝试找到解决方案。

[1] 额外说明：如果你特别聪明的话，你还可以把B放进传给C的递归调用的列表里，把B和C放进传给D的列表里。

Answer 2

维基百科上其实有一些很不错的伪代码，用于深度优先遍历。这些遍历算法会给图中的所有节点标上它们在遍历中出现的顺序。不过，你想要的是一旦找到目标就立即返回到目标的路径。

所以我们来修改一下维基百科的算法：

( INCORRECT ALGORITHM DELETED WHICH THE OP COMMENTED ON CORRECTLY BELOW )

这里有一个用Python实现的例子：

g = {
    'A': ['B', 'C', 'D'],
    'B': ['C', 'E', 'F'],
    'C': ['A'],
    'D': ['B', 'F', 'G', 'H'],
    'E': ['G'],
    'F': ['A', 'F'],
    'G': ['H', 'I'],
    'H': [],
    'I': []
}

def DFS(g, v, goal, explored, path_so_far):
    """ Returns path from v to goal in g as a string (Hack) """
    explored.add(v)
    if v == goal: 
        return path_so_far + v
    for w in g[v]:
        if w not in explored:
            p = DFS(g, w, goal, explored, path_so_far + v)
            if p: 
                return p
    return ""

# Hack unit test
assert DFS(g, 'A', 'I', set(), "") == "ABEGI"
assert DFS(g, 'A', 'E', set(), "") == "ABE"
assert DFS(g, 'B', 'B', set(), "") == "B"
assert DFS(g, 'B', 'B', set(), "") == "B"
assert DFS(g, 'A', 'M', set(), "") == ""
assert DFS(g, 'B', 'A', set(), "") == "BCA"
assert DFS(g, 'E', 'A', set(), "") == ""

这个思路是，你想在图 g 中找到从 v 到 goal 的路径，前提是你已经沿着 path_so_far 这条路径走过了。其实 path_so_far 应该在 v 之前结束。

如果 v 就是目标，那你可以把 v 加到当前路径中，这样就完成了。

如果不是的话，你需要探索从 v 出发的所有边，这些边的另一端没有已经探索过的节点。对于每一条这样的边，你可以用当前的路径加上当前节点来进行递归搜索。如果从 v 到目标没有路径，你就返回一个空路径。

好的一点是，你在使用递归来“自动回溯”，因为你把扩展后的路径传递给了递归调用。