Теория графов DFS получает путь от начального до конечного узла - PullRequest
Новая
       8

Теория графов DFS получает путь от начального до конечного узла

0 голосов
/ 05 января 2019

Мне нужен только один путь от источника к узлу назначения, чтобы вернуться из этой функции, но эта функция не останавливается после обнаружения пути. Я использовал возврат только когда конечный узел найден. как я могу закончить это, когда путь найден. в моей ситуации только один путь, и никаких петель один узел имеет максимум 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}")

1 Ответ

0 голосов
/ 05 января 2019

проблема решена, просто нужно получить возвращаемую переменную из функции и сравнить ее 

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}")
...