Изменить первый алгоритм глубины из рекурсии на итерацию

Question

Я пытаюсь вычислить способ преобразования функции helper из рекурсии на итерацию, используя некоторую форму цикла.

На самом деле я на самом деле тупик, и мне интересно, могут ли кто-нибудь из вас помочь. Это функция, созданная для поиска, если заданный путь начала и конца точки существует в ориентированном графе, используя первый обход глубины.

def helper(graph, current, visited): 
    if current in graph: 
     for neighbor in graph[current]: 
      if neighbor not in visited: 
       visited.append(neighbor) 
       helper(graph, neighbor, visited) 

def DFS(graph, start, goal): 
    if start not in graph and goal not in graph: 
     return False 
    visited = [start] 
    helper(graph, start, visited) 
    return goal in visited 

Answer 1

Решение использует явный стек:

stack = [start] 
while len(stack) > 0: 
    node = stack.pop() 
    for x in graph[node]: 
     if x not in visited: 
      visited.add(x) 
      stack.append(x) 

В качестве примечания ваш код использует список для visited и это будет делать вещи O(n^2) медленно, вы можете использовать вместо set. Также вы можете сразу же выйти на поиски цели, если проверка наличия/отсутствия - это все, что вам нужно от вашего поиска.

Answer 2

Сначала вам понадобится стек для глубины (или очередь для первой ширины).

def helper(graph, start, visited): 
    stack = [ start ] 
    while len(stack) > 0: 
     current = stack.pop() 
     if current in graph: 
      for neighbor in graph[current]: 
       if neighbor not in visited: 
        visited.append(neighbor) 
        stack.append(neighbor)