Уменьшите использование памяти для поиска в ширину ⇐ 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 =
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