如果发现距离后问题在于重构路径，请按以下方式调整BFS：从要连接的两个顶点之一开始，进行BFS。对于
v发现的每个顶点，请存储其前驱体：如果
w通过边发现顶点
u->w，则的前驱体
w为
u。然后，可以从目标顶点开始，从前一个顶点到另一个前一个顶点，直到到达源顶点为止，然后以相反的顺序重建路径。
例：
J A / / B C / / D E F / / G H I
如果您计算从
D到的路径
I，那么您将具有以下前身：
pre[I]=Gpre[G]=Fpre[F]=Cpre[C]=Apre[A]=B //A was discovered during the BFS via the edge B->A, so pre[A]=Bpre[B]=D
您还会有一些前辈不在您的道路上，因此它们在重建期间不会有任何问题。在示例中，您还将拥有
pre[J]=Apre[E]=Bpre[H]=F
但是对于从BFS的源
D到目标的路径，
I您在重建期间将无法实现。
当您重建从开始的路径时
I，您会得到
I<-G，然后是
I<-G<-F，依此类推，直到您拥有相反顺序的完整路径。
如果只关心到一个目标的路径，则一旦发现目标，就可以中止BFS；否则，您可以终止BFS。但是，这不会改变复杂性。但是，如果要从一个源顶点到所有目标的路径，请执行完整的BFS；如果这样做，那么前任版本将允许您重构到任何目标顶点的路径。
