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

Question

我整个星期都在尝试这个,但是,对于我的生活,我不能想出来.

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

我很困惑,除了递归之外,我甚至无法确切地解决问题.

谢谢你的帮助.

编辑:好的,我会澄清一点.令我困惑的一件事是当节点没有邻居时返回什么路径.可以首先返回目标路径,但是,因为帮助程序仍在递归,它可以返回死端路径.我想我对回溯感到困惑.

Answer 1

维基百科实际上有一些非常好的伪代码用于深度优先遍历.这些遍历算法使用它们在遍历中出现的顺序标记图中的所有节点.相反,您希望在找到目标时立即返回目标的路径.

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

( 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则返回空路径.

好处是你使用递归来"自动回溯",因为你将增强的路径传递给你的递归调用.