Реализация BFS алгоритм с максимальной глубиной и которая печатает все кратчайшие пути

Question

Это алгоритм BFS я придумал, чтобы напечатать все кратчайшие пути от корневого узла к любому другому узлу в графе:

d = deque() 
d.append(root) 
level = 0 
while len(d) >= 0 and level <= max_depth: 
    u = d.popleft() 
    print(adjacency_list[u]) 
    for v in adjacency_list[u]: 
     if visited[v] == 'N': 
      if nodes2distances[u] + 1 <= nodes2distances[v]: 
       nodes2distances[v] = nodes2distances[u] + 1 
       node2parents[v].append(u) 
       d.extend(v) 
    level += 1 
    visited[u] = 'Y' 

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

1) Не могли бы вы объяснить, как я мог реализовать этот алгоритм с ограничением уровня (т. Е. Указав максимальный уровень)?

2) Кроме того, не могли бы вы сообщить мне, если подход, который я принял для решения проблемы, может быть лучше?

Редактировать: ОК. Извините, я этого не делал раньше! Скажем, у меня есть следующие ребра в виде невзвешенном графа:

('A', 'B'), ('A', 'C'), ('B', 'C'), ('B '', 'D'), ('D', 'E'), ('D', 'F'), ('D', 'G'), ('E', 'F'), ('G »,„F“)

После реализации моего кода без ограничения глубины, я получаю следующий результат, когда я вызвать алгоритм для узла „B“,

[('A', ['B']), ('C', ['B']), ('D', ['B']), ('E', ['D']), ('F', ['D']), ('G', ['D'])] 

Однако, когда я вызывать ту же функцию с ограничением уровня 2, то есть myFunction(graph,'E',2), я получаю следующий результат:

[('A', ['B']), ('C', ['B']), ('D', ['B'])] 

тогда, ожидаемый выход на

[('A', ['B']), ('C', ['B']), ('D', ['B']),('E',['D']),('F', ['D']),('G',['D'])] 

Answer 1

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

d = deque() 
      #node,level 
d.append((root,0 )) 
while len(d) >= 0: 
    front = d.popleft() 
    u = front[0] 
    level = front[1] 
    if level >= max_depth: 
     break 
    print(adjacency_list[u]) 
    for v in adjacency_list[u]: 
     if visited[v] == 'N': 
      if nodes2distances[u] + 1 <= nodes2distances[v]: 
       nodes2distances[v] = nodes2distances[u] + 1 
       node2parents[v].append(u) 
       d.append((v,level+1)) 
    visited[u] = 'Y'