时间戳

首页 > 解决方案 > Python 深度优先搜索在找到时停止

python - Python 深度优先搜索在找到时停止

问题描述

我有这个问题。当搜索区域的上述坐标的网格状态== 5时，表示停止并移动到该位置。出于某种原因，它继续存在，我一直在试图找出原因。我假设其他人的眼睛看着它会很明显！

def depthfirstsearch(visited,graph,vertex):
    # Do a depth-first search of all neighbours if found stop.
    moveto(vertex,3)
    visited.append(vertex)
    if (the_maze.grid[vertex[0] - 1][vertex[1]].status) == 5:
        x = vertex[0] - 1
        y = vertex[1]
        moveto((x, y), 0)
        return
    else:
        for neighbour in graph[vertex]:
            if neighbour not in visited:
                depthfirstsearch(visited, graph, neighbour)

标签： pythonpython-3.xdepth-first-search

解决方案

您的函数在找到目标时返回。

if (the_maze.grid[vertex[0] - 1][vertex[1]].status) == 5:
    # ..
    return

但是，它返回None并且递归调用对它返回的事实没有任何作用：

if neighbour not in visited:
    depthfirstsearch(visited, graph, neighbour)

如果此调用depthfirstsearch()找到目标，您希望该函数也返回一个肯定的结果。如果调用没有找到它，你会希望它继续搜索。

因此，您需要：

if (the_maze.grid[vertex[0] - 1][vertex[1]].status) == 5:
    # ..
    return True

和：

if neighbour not in visited:
    if depthfirstsearch(visited, graph, neighbour):
        return True

最后，您可以依赖函数None在它完成时返回而无需显式返回，但这有点难看。None评估False为 a bool，但为了清晰和类型安全，您也可以return False在最后。

所以，结果：

def depthfirstsearch(visited,graph,vertex):
    # Do a depth-first search of all neighbours if found stop.
    moveto(vertex,3)
    visited.append(vertex)
    if (the_maze.grid[vertex[0] - 1][vertex[1]].status) == 5:
        x = vertex[0] - 1
        y = vertex[1]
        moveto((x, y), 0)
        # found it, report success
        return True
    else:
        for neighbour in graph[vertex]:
            if neighbour not in visited:
                if depthfirstsearch(visited, graph, neighbour):
                    # found in recursion, report success
                    return True
    # if this point is reached, this call didn't find it anywhere
    return False

推荐阅读