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

Question

我整个星期都在尝试这个，但我这辈子都弄不明白。

我知道我需要一个辅助函数来递归并返回 pathSoFar。我似乎无法理解递归。

我很困惑，除了递归之外，我什至无法准确地表述出问题是什么。

感谢您的帮助。

编辑:好的，我会澄清一点。让我感到困惑的一件事是当节点没有邻居时返回什么路径。目标路径可能首先返回，但是随后，因为助手仍在递归，它可以返回死胡同的路径。我想我对回溯感到困惑。

Answer 1

Wikipedia实际上有一些非常好的深度优先遍历伪代码。这些遍历算法用它们在遍历中出现的顺序标记图中的所有节点。相反，您希望在找到目标后立即返回到目标的路径。

那么让我们修改维基百科算法:

( 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 到目标的路径，您将返回一个空路径。

好处是您使用递归来“自动回溯”，因为您将扩充路径传递到递归调用中。