无法反向遍历场景下，如何用BFS结合记忆化/DP求顶点到目标的距离

当然可以做到！虽然你没法直接从D反向遍历，但我们可以结合正向BFS+记忆化动态规划的思路，在不违反你现有BFS实现逻辑的前提下，高效算出所有可达节点到D的距离。

你的BFS逻辑是弹出节点v后才获取邻居，那我们可以分两步走：

1. 先完成一次正向BFS，完整记录所有节点的后继关系（也就是每个节点能到达的邻居），同时覆盖所有从A可达的节点；
2. 基于记录的后继关系，用记忆化/DP的方式从目标节点D反向推导每个节点到D的距离——这里的“反向”不是遍历原图的反向边，而是利用已记录的拓扑关系，从后往前计算距离。

步骤1：正向BFS记录后继关系 #

先执行从A出发的BFS，弹出节点时记录它的所有邻居，把整个可达子图的结构存下来。这一步完全符合你“弹出节点后才确定邻居”的要求。

伪代码示例：

from collections import deque

def bfs_record_successors(start_node, get_neighbors_func):
    queue = deque([start_node])
    visited = set([start_node])
    successors = {}  # 键是节点，值是该节点的所有邻居列表

    while queue:
        current_node = queue.popleft()
        # 弹出后才获取邻居，完全匹配你的实现逻辑
        neighbors = get_neighbors_func(current_node)
        successors[current_node] = neighbors
        
        for neighbor in neighbors:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    
    return successors

这里的get_neighbors_func就是你用来获取节点邻居的自定义函数，直接对接你现有的逻辑即可。

步骤2：记忆化DP计算到D的距离 #

有了后继关系后，我们可以用两种方式计算距离，选哪种取决于你的图规模和偏好：

方式A：递归+记忆化（简洁直观） #

用递归从每个节点出发，查询它的后继节点到D的距离，再+1得到当前节点的距离，同时用缓存避免重复计算：

from functools import lru_cache

def compute_distances(successors, target_node):
    @lru_cache(maxsize=None)
    def dp(node):
        if node == target_node:
            return 0
        # 若节点无法到达D，返回无穷大表示不可达
        min_distance = float('inf')
        for neighbor in successors.get(node, []):
            neighbor_dist = dp(neighbor)
            if neighbor_dist != float('inf'):
                min_distance = min(min_distance, neighbor_dist + 1)
        return min_distance
    
    # 遍历所有可达节点，计算到D的距离
    distance_map = {}
    for node in successors.keys():
        distance_map[node] = dp(node)
    
    return distance_map

方式B：迭代式拓扑排序（避免递归栈溢出） #

如果你的图节点很多，递归可能栈溢出，那可以用拓扑排序的思路，从D出发，依次处理它的前驱节点：

from collections import deque

def compute_distances_iterative(successors, target_node):
    # 先构建反向邻接表：键是节点，值是所有指向它的前驱节点
    reverse_adj = {}
    for node, neighbors in successors.items():
        for neighbor in neighbors:
            if neighbor not in reverse_adj:
                reverse_adj[neighbor] = []
            reverse_adj[neighbor].append(node)
    
    distance_map = {target_node: 0}
    queue = deque([target_node])
    
    while queue:
        current_node = queue.popleft()
        # 处理所有前驱节点
        for prev_node in reverse_adj.get(current_node, []):
            if prev_node not in distance_map:
                # 因为是有向图，前驱节点到D的距离 = 当前节点距离 +1
                distance_map[prev_node] = distance_map[current_node] + 1
                queue.append(prev_node)
    
    # 给无法到达D的节点标记无穷大
    for node in successors.keys():
        if node not in distance_map:
            distance_map[node] = float('inf')
    
    return distance_map

你的图是A->B->C->D，用上面的方法：

1. 正向BFS会记录successors[A] = [B], successors[B] = [C], successors[C] = [D], successors[D] = []；
2. 计算距离时：
   • distance[D] = 0
   • distance[C] = 0 +1 =1
   • distance[B] =1 +1=2
   • distance[A] =2 +1=3
     完全符合你的需求，而且整体时间复杂度是O(N+E)，非常高效。

• 如果你的图存在环，需要提前判断节点是否能到达D，避免无效计算（两种方法都已经处理了不可达的情况，返回无穷大）；
• 整个流程完全不需要反向遍历原图，完美适配你“弹出节点后才确定邻居”的限制。

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