为什么深度优先搜索时我的 for 循环没有中断

Question

我正在使用 python 进行深度优先搜索。要做到这一点，有一个 graph 和一些我必须显示路径的值，在给定的初始位置，到达最终目的地

visited = set()

def dfs(visited, graph, initial, final):
    if initial not in visited:
        print (initial)
        visited.add(initial)
        for neighbour in graph[initial]:
            if(final == initial):
                print("a")
                break
            dfs(visited, graph, neighbour, final)
    return visited

dfs(visited, graph, 'arad', 'lugoj')

问题出在for里面的if。当我的 final 位置等于当前位置（这意味着我到达目的地）时，我想打破它，并且 return 返回一个包含到达它的路径的列表。但它不会中断，也不会 return 任何东西，控制台中显示的唯一值是 prints inside 方法。这是控制台：

arad
timisoara
lugoj
a
sibiu
oradea
zerind
rimnicu vilcea
craiova
pitesti
bucharest
fagaras
giurgiu
urziceni
vaslui
lasi
neamt
hirsova
eforie
dobreta
mehadia

如您所见，它必须在 'a' 中中断。

我该如何处理？

##更新

{'timisoara', 'pitesti', 'eforie', 'lasi', 'craiova', 'mehadia', 'arad', 'urziceni', 'lugoj', 'neamt', 'dobreta', 'zerind', 'giurgiu', 'rimnicu vilcea', 'bucharest', 'fagaras', 'sibiu', 'vaslui', 'hirsova', 'oradea'}

图表

#DEPTH_FIRST_SEARCH
graph = {
    'oradea' : ['zerind','sibiu'],
    'zerind' : ['arad', 'oradea'],
    'arad' : ['timisoara', 'sibiu', 'zerind'],
    'timisoara' : ['lugoj', 'arad'],
    'lugoj' : ['mehadia', 'timisoara'],
    'mehadia' : ['dobreta', 'lugoj'],
    'dobreta' : ['craiova', 'mehadia'],
    'craiova' : ['pitesti', 'rimnicu vilcea', 'dobreta'],
    'rimnicu vilcea' : ['craiova', 'pitesti', 'sibiu', ],
    'sibiu' : ['oradea', 'arad', 'rimnicu vilcea', 'fagaras'],
    'fagaras' : ['sibiu', 'bucharest'],
    'pitesti' : ['rimnicu vilcea', 'craiova', 'bucharest'],
    'bucharest' : ['fagaras', 'pitesti', 'giurgiu', 'urziceni'],
    'giurgiu' : ['bucharest'],
    'urziceni' : ['bucharest', 'vaslui', 'hirsova'],
    'vaslui' : ['lasi', 'urziceni'],
    'lasi' : ['neamt', 'vaslui'],
    'hirsova' : ['urziceni', 'eforie'],
    'eforie' : ['hirsova'],
    'neamt' : ['lasi']
}

Answer 1

问题是你只是在递归调用中跳出循环，而不是调用者。

由于您是就地修改 visited，因此没有必要 return。

相反，您可以 return 一个指示是否找到 final 的布尔值，调用者也可以跳出他们的循环。

另外，final 和 initial 在循环中不会改变，所以没有必要在那里比较它们。在循环之前做。

def dfs(visited, graph, initial, final):
    if initial not in visited:
        print (initial)
        visited.add(initial)
        if(final == initial):
            print("a")
            return True
        for neighbour in graph[initial]:
            if dfs(visited, graph, neighbour, final):
                return True
    return False

为什么深度优先搜索时我的 for 循环没有中断

Why isnt my for loop breaking while Depth First Search

python

for-loop

depth-first-search