python-3.x 为什么我的深度优先搜索即使在找到目标后仍继续工作?

ds97pgxw  于 2022-11-26  发布在  Python
关注(0)|答案(1)|浏览(110)

我正在建立一个深度优先搜索函数,它是用于无向邻接表的,这个函数的目的是把所有成功找到目标节点的路径放入可行函数表中,而把不可行的路径放入死胡同中。

adjacencylist={1:[2,3],2:[1,4],3:[1,5],4:[2],5:[3]}
visited=[]
culdesacs=[]
viablepaths=[]
def dfs(graph,node,target,path,output):
    if node in visited:
        return
    visited.append(node)
    print(path)
    
    if node==target:
        output.append(path)
        viablepaths.append(output)
        
        return print('hello')
    for nx in graph[node]:
        dfs(graph,nx,5,path+[nx],output)
    for element in path:
        if element not in culdesacs:
            culdesacs.append(element)
    print(path)
    print(culdesacs)
    return print('oops')

dfs(adjacencylist,1,5,[1],[])

我不明白的是,为什么我的函数在成功命中目标甚至触发递归程序的基本情况后仍然继续工作。(adjacencylist,1,5,[1],[]),我的起始节点是1,我的目标节点是5。我的函数成功地找到了路径[1,3,5]并返回“hello”。但随后它继续输出oops并输出路径[1,3]和[1]。理想情况下,一旦它找到路径[1,3,5],我希望它完全结束函数
如何解决此问题

wpx232ag

wpx232ag1#

问题如下:当你在

for nx in graph[node]:
        dfs(graph,nx,5,path+[nx],output)

启动查找目标的递归调用。但是,在

if node==target:
        output.append(path)
        viablepaths.append(output)
        
        return print('hello')

并且不检查返回值。
我建议你仔细阅读调用栈的行为。仅仅因为你结束了找到值的递归调用,其他的调用并没有被取消

相关问题