Уменьшите использование памяти для поиска в ширину ⇐ Python

[Anonymous]

Я новичок в компьютерных науках. Я изо всех сил пытался уменьшить использование памяти при выполнении поиска в ширину.
Для демонстрации:
Для ориентированного ациклического графа (DAG). от Кормена и др. Найдите все уникальные пути от источника (1) до приемника (6).
вершины: [1, 2, 3, 4, 5, 6]
ребра: [(1, 2), (1, 3), (2, 4), (3, 2), (3, 5), (4, 6), (5, 4), (5, 6)]
Та же информация, что и в карте смежности (словарь Python):
adj = {1:[2, 3], 2:[ 4], 3:[2, 5], 4:[6], 5:[4, 6]
В приведенном ниже коде я сохраняю путь как список ребер.
В очереди две вещи: следующее ребро, добавляемое к пути, и путь на данный момент.
По мере того, как количество ребер становится 1800 или около того, требования к памяти для этого кода становятся более 500 МБ. Очередь использует больше всего памяти.
Есть ли способ сделать BFS с гораздо меньшим использованием памяти?

Код: Выделить всё

def BFS(adj):
all_paths = []
for v in adj[1]:
queue = deque()
queue.append(((1, v),[]))
while queue:
(w, x), path = queue.pop()
path.append((w, x))
if x not in adj.keys():
continue
for y in adj[x]:
if y == n: # reached sink
# convert list of edges to final - a list of vertices
path.append((x, y))
a = path[0][0]
final = [a]
for e in path:
final.append(e[1])
if final not in all_paths:
all_paths.append(final)
continue
elif (x, y) not in path:
tmp = [i for i in path]
queue.appendleft(((x,y), tmp))

return all_paths

Ожидаемый результат:
[[1, 2, 4, 6], [1, 3, 5, 6], [1, 3, 2, 4, 6 ], [1, 3, 5, 4, 6]]

Подробнее здесь: https://stackoverflow.com/questions/790 ... rst-search