Как отслеживать глубину узла в DFS без рекурсии (используя стек)?

Question

Это мой фрагмент кода для DFS без рекурсии в python:

 def DFS(graph,start,end):
explored=[]
queue=[[start]]

if start == end:
    return "done"
while queue:
    path=queue.pop()
    node=path[-1]
    if node not in explored:
        neighbours=graph[node]

        for neighbour in neighbours:
            new_path=list(path)
            new_path.append(neighbour.name)
            queue.append(new_path)
            if neighbour.name== end:
                return new_path
        explored.append(node)
return "no path"

Вот так выглядит мой узел: edge edge: #def init ():

def __init__(self,name,value,depth=0):
    self.name=name
    self.value=value
    self.depth=depth

Как отслеживать уровни каждого узла, так как я должен реализовывать поиск с ограниченной глубиной без рекурсии?

Answer 1

В вашем текущем алгоритме нет способа подсчета уровней, поскольку вы не отслеживаете достаточно информации в алгоритме.

Как вы говорите, отслеживать уровни намного проще при выполнении рекурсии.Разница между рекурсией и взаимодействием не так уж велика.Вы обмениваетесь вызовом функции для цикла и некоторой незначительной реструктуризацией своего кода, чтобы компенсировать цикл.

Вы все равно сможете выяснить текущую глубину, даже если у вас есть итеративный алгоритм.Если вы начнете с рекурсивной версии и продолжите свой путь к итеративному решению, сохраняя при этом глубокие знания, то я думаю, что вы решите его.

Мне кажется, что это школьная работа, поэтому я не дам вамрешение.Надеюсь, вы понимаете.

Один совет может содержать не только путь в вашей очереди, но и глубину, например, в виде кортежа.