数据结构与算法 / 系统课时
遍历中怎样恢复具体路径
遍历中怎样恢复具体路径
只知道“终点可达”还不够,很多题目还要求输出从起点到终点经过了哪些节点。最稳妥的做法是在 BFS 或 DFS 首次发现节点时记录它的前驱,遍历结束后从终点沿前驱反向追溯,再翻转得到一条合法路径。
学习目标
- 理解前驱数组或前驱映射为什么足以恢复路径。
- 能在 BFS 中记录前驱并重建一条从起点到终点的路径。
- 能处理起点等于终点、目标不可达等边界情况。
前驱记录保存了什么
遍历图时,访问到节点 v 的那一刻,必然是从某个已访问节点 u 走到 v。只要记录 parent[v] = u,就保存了“这次发现是从哪里来的”。对起点设置特殊前驱,例如 None,就能把这些局部关系串成一棵以起点为根的遍历树。
对于 BFS,节点第一次被发现时对应的是最少边数路径上的前驱,因此在无权图中可以恢复一条最短路径。DFS 同样能恢复路径,但通常只保证路径合法,不保证边数最少。

用 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,而不是强行追溯。
路径恢复的额外空间主要是前驱表和最终路径,最坏都是 ;重建阶段只沿最终路径回退,若路径长度为 ,耗时为 。
按自己的节奏,确认真正理解。