图论DFS从节点开始到结束的路径

Question

我只需要一条从源节点到目标节点的路径，就可以从这个函数返回，但是这个函数在发现路径之后不会停止。 我只在找到结束节点时使用return。 找到路径后我该怎么结束这一切呢。 我的处境只有一条路，没有循环 一个节点最多有4个子节点

def  dfs(gpdic,start,end,visited,path):
   visited[start] = 1
   path.append(start)
   print(f"start node {start}")

   if start == end:
       print(f"this is the path {path}")
       return path
   else:
       print(f"stack {path}")
       for node in gpdic[start]:
           print(f" in node - {node}")
           if visited[node]== -1 and node != -1 and node != 0 :
               print(f" calling for next recursive funtion {node} ")
               dfs(gpdic,node,end,visited,path)
               #return path
    po =  path.pop()
    print(f" poped last {po}")
    visited[start] = -1

if __name__ == '__main__':
    gp = {1: [2, -1, -1, -1], 2: [3, 4, 1, 5], 3: [6, -1, 2, 7],
    4:[-1, -1, -1, 2], 5: [-1, 2, -1, -1], 6: [-1, -1, 3, -1],
    7[-1, 3, -1, -1]}


    visited = [-1] * 12
    path = []
    pathret = dfs(gp,7,4,visited,path)
    print(f"finale path - > {pathret}")

Answer 1

解决问题只需从函数中获取返回变量并进行比较

def dfs(gpdic,start,end,visited,path):
   visited[start] = 1
   path.append(start)
   print(f"start node {start}")

   if start == end:
       print(f"this is the path {path}")
       return path
   else:
       print(f"stack {path}")
       for node in gpdic[start]:
           print(f" in node - {node}")
           if visited[node]== -1 and node != -1 and node != 0 :
               print(f" calling for next recursive funtion {node} ")
               l = dfs(gpdic,node,end,visited,path)
               if l is not None:
                   return path
    po =  path.pop()
    print(f" poped last {po}")
    visited[start] = -1

if __name__ == '__main__':
    gp = {1: [2, -1, -1, -1], 2: [3, 4, 1, 5], 3: [6, -1, 2, 7],
    4:[-1, -1, -1, 2], 5: [-1, 2, -1, -1], 6: [-1, -1, 3, -1],
    7[-1, 3, -1, -1]}


visited = [-1] * 12
path = []
pathret = dfs(gp,7,4,visited,path)
print(f"finale path - > {pathret}")