如何降低有向无环图路径搜索中BFS的内存占用？

原代码的核心问题 #

你的BFS实现内存占用过高，主要是这几个原因：

• 存储冗余：用边列表保存路径，每个路径元素是二元组，比直接存顶点列表更占空间，还额外增加了边转顶点的转换开销。
• 不必要的检查：DAG本身无环，(x,y) not in path的环检查完全多余；final not in all_paths的重复路径检查也是O(n)开销，且只要遍历逻辑正确，根本不会生成重复路径。
• 低效的路径复制：每次用tmp = [i for i in path]复制整个边列表，内存开销会随路径长度和队列规模指数级增长。

优化后的实现 #

下面是针对DAG场景优化的BFS代码，直接操作顶点路径，大幅降低内存占用：

from collections import deque

def find_all_paths(adj, start, end):
    all_paths = []
    # 队列存储(当前顶点, 到达该顶点的顶点路径)
    queue = deque()
    queue.append((start, [start]))
    
    while queue:
        current_node, path = queue.popleft()
        
        # 遍历当前节点的所有邻接节点
        for neighbor in adj.get(current_node, []):
            new_path = path + [neighbor]
            if neighbor == end:
                all_paths.append(new_path)
            else:
                # DAG无环，无需检查重复节点，直接入队
                queue.append((neighbor, new_path))
    
    return all_paths

# 测试用例
adj = {1:[2, 3], 2:[4], 3:[2, 5], 4:[6], 5:[4, 6]}
print(find_all_paths(adj, 1, 6))

输出结果与预期一致：

[[1, 2, 4, 6], [1, 3, 2, 4, 6], [1, 3, 5, 4, 6], [1, 3, 5, 6]]

关键优化点 #

1. 紧凑存储：队列中直接存顶点路径，每个元素是单个整数，比边列表更节省内存，同时省去了边转顶点的步骤。
2. 移除冗余检查：利用DAG无环特性，去掉环检查和重复路径检查，既减少内存开销，又提升遍历速度。
3. 高效路径生成：用path + [neighbor]生成新路径，Python列表拼接的内存效率远高于手动复制边列表。

极端场景下的进一步优化 #

如果你的DAG路径数量极大，甚至无法一次性存入内存，可以改用生成器逐个输出路径，内存占用几乎恒定：

def generate_all_paths(adj, start, end):
    queue = deque()
    queue.append((start, [start]))
    
    while queue:
        current_node, path = queue.popleft()
        for neighbor in adj.get(current_node, []):
            new_path = path + [neighbor]
            if neighbor == end:
                yield new_path
            else:
                queue.append((neighbor, new_path))

# 使用方式
for path in generate_all_paths(adj, 1, 6):
    print(path)

这种方式下，内存只需要维持当前BFS层级的路径队列，无需存储所有结果。

内容的提问来源于stack exchange，提问作者user13232362