数据结构与算法 / 系统课时

遍历中怎样恢复具体路径

遍历中怎样恢复具体路径

只知道“终点可达”还不够,很多题目还要求输出从起点到终点经过了哪些节点。最稳妥的做法是在 BFS 或 DFS 首次发现节点时记录它的前驱,遍历结束后从终点沿前驱反向追溯,再翻转得到一条合法路径。

学习目标

  • 理解前驱数组或前驱映射为什么足以恢复路径。
  • 能在 BFS 中记录前驱并重建一条从起点到终点的路径。
  • 能处理起点等于终点、目标不可达等边界情况。

前驱记录保存了什么

遍历图时,访问到节点 v 的那一刻,必然是从某个已访问节点 u 走到 v。只要记录 parent[v] = u,就保存了“这次发现是从哪里来的”。对起点设置特殊前驱,例如 None,就能把这些局部关系串成一棵以起点为根的遍历树。

对于 BFS,节点第一次被发现时对应的是最少边数路径上的前驱,因此在无权图中可以恢复一条最短路径。DFS 同样能恢复路径,但通常只保证路径合法,不保证边数最少。

BFS 前驱记录与反向重建路径

用 BFS 记录并恢复路径

下面的完整示例使用邻接表执行 BFS。关键点是只在节点第一次入队时写入 parent,避免后续路径覆盖已经确定的最短路前驱。

python
from collections import deque


def bfs_path(graph, start, target):
    queue = deque([start])
    parent = {start: None}

    while queue:
        current = queue.popleft()
        if current == target:
            break

        for neighbor in graph.get(current, []):
            if neighbor not in parent:
                parent[neighbor] = current
                queue.append(neighbor)

    if target not in parent:
        return None

    # 从终点沿前驱回退,再反转成起点到终点的顺序。
    path = []
    current = target
    while current is not None:
        path.append(current)
        current = parent[current]

    path.reverse()
    return path


def main():
    graph = {
        "S": ["A", "B"],
        "A": ["C"],
        "B": ["C"],
        "C": ["T"],
        "T": [],
    }

    print(bfs_path(graph, "S", "T"))


if __name__ == "__main__":
    main()

预期输出

text
['S', 'A', 'C', 'T']

因为 BFS 先经 S -> A 发现 A,再经 A -> C 首次发现 C,所以最终记录的前驱链为 T <- C <- A <- S。实际存在多条同长度最短路径时,具体恢复哪一条取决于邻接表中的遍历顺序。

重建路径时的边界

起点就是终点时,parent 中一开始已有起点,反向重建会得到只含一个节点的路径。目标不可达时,遍历结束后目标不会出现在 parent 中,应直接返回空结果或 None,而不是强行追溯。

路径恢复的额外空间主要是前驱表和最终路径,最坏都是 O(V)O(V);重建阶段只沿最终路径回退,若路径长度为 LL,耗时为 O(L)O(L)。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

遍历中怎样恢复具体路径

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通