如何修改有向图BFS算法以保存/打印源节点出发的所有路径？

嘿，这个问题我熟！你现在的BFS能遍历到所有可达节点，但没法记录每条具体路径对吧？其实核心就是把BFS队列里的单个节点，换成从起点到当前节点的完整路径——这样每一步都能跟踪到走到当前节点的具体路线，自然就能保存或打印所有路径了。

核心思路 #

传统BFS的队列只存放单个节点，我们需要调整队列元素为路径集合（比如列表/数组），每个元素都是从起点到当前节点的完整路径。每次处理队列中的路径时：

1. 直接保存或打印这条路径（如果需要记录所有路径）
2. 遍历当前节点的所有邻居，把邻居添加到路径末尾形成新路径，再将新路径加入队列
3. 注意处理图中的环：如果邻居已经在当前路径里，跳过它，避免无限循环

代码示例（Python） #

下面是一个完整的实现，既能保存所有路径，也能直接打印：

from collections import deque

def bfs_all_paths(graph, start):
    # 队列中存储的是完整路径，初始路径只有起始节点
    queue = deque([[start]])
    all_paths = []  # 用来保存所有找到的路径

    while queue:
        current_path = queue.popleft()
        current_node = current_path[-1]

        # 保存当前路径到结果集，也可以直接print(current_path)
        all_paths.append(current_path)

        # 遍历当前节点的所有邻居
        for neighbor in graph.get(current_node, []):
            # 避免环：如果邻居已经在当前路径中，跳过
            if neighbor not in current_path:
                # 复制当前路径并添加邻居，生成新路径
                new_path = current_path.copy()
                new_path.append(neighbor)
                queue.append(new_path)
    
    return all_paths

# 测试用例：一个简单的有向图
graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}

# 调用函数并打印所有路径
start_node = 'A'
paths = bfs_all_paths(graph, start_node)
for idx, path in enumerate(paths, 1):
    print(f"路径{idx}: {' -> '.join(path)}")

关键细节说明 #

• 队列存路径而非节点：这是实现保存路径的核心，每个队列元素都携带了从起点到当前节点的完整路线。
• 路径复制：必须创建路径的副本（比如current_path.copy()），因为列表是可变对象，如果直接修改原路径会影响队列中其他元素。
• 环的处理：if neighbor not in current_path的判断能防止图中出现环时无限生成重复路径（比如A→B→A→B...）。
• 目标路径筛选：如果你只需要保存到特定目标节点的所有路径，只需在处理路径时判断当前节点是否为目标，是的话再加入结果集，示例如下：

def bfs_target_paths(graph, start, target):
    queue = deque([[start]])
    target_paths = []

    while queue:
        current_path = queue.popleft()
        current_node = current_path[-1]

        # 找到目标节点，保存路径
        if current_node == target:
            target_paths.append(current_path)
            continue  # 如果目标节点没有出边，可直接跳过后续遍历

        for neighbor in graph.get(current_node, []):
            if neighbor not in current_path:
                new_path = current_path.copy()
                new_path.append(neighbor)
                queue.append(new_path)
    
    return target_paths

这个思路适用于所有编程语言，比如Java可以用Queue<List<Node>>，C#用Queue<List<T>>，核心逻辑完全一致。

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