0

给定两个顶点（A 和 B）和一棵树（G）（无向简单图） - 在 G 中的 A 和 B 之间的简单路径中找到顶点。算法应该以 O(V) 复杂度运行。

例如 - 在 a 和 b 之间的简单路径中找到顶点：

d<->k
k<->a
k<->b

答案应该是：k

我试图修改 BFS 以实现目标，但到目前为止它似乎没有奏效。

有什么建议么？

4

1 回答 1

3

如果问题是在找到距离后重建路径，请按以下方式调整 BFS：从要连接的两个顶点之一开始，执行 BFS。对于您发现的每个顶点v，存储其前身：如果您w通过边发现顶点u->w，那么前身w是u。之后，您可以通过从目标顶点开始并从前一个顶点到前一个顶点，直到到达源顶点，以相反的顺序重建路径。

例子：

     J
      \
       \
        A
       / \
      /   \
     B     C
    / \     \
   /   \     \
  D     E     F
             / \
            /   \
           G     H
            \
             \
              I

如果你计算从D到的路径I，那么你有以下前辈：

pre[I]=G
pre[G]=F
pre[F]=C
pre[C]=A
pre[A]=B        //A was discovered during the BFS via the edge B->A, so pre[A]=B
pre[B]=D

您还将有一些前辈不在您的道路上，因此在重建过程中它们无关紧要。在示例中，您还将拥有

pre[J]=A
pre[E]=B
pre[H]=F

但是对于从 BFS 的源D到目标的路径，I您在重建过程中不会遇到它们。

当您重建从 开始的路径时I，您会得到I<-G，然后I<-G<-F是 ，依此类推，直到您以相反的顺序获得完整路径。

如果你只关心一个目标的路径，你可以在发现目标后中止 BFS；但这不会改变复杂性。但是，如果您想要从一个源顶点到所有目标的路径，请执行完整的 BFS；如果你这样做，前辈将允许你重建任何目标顶点的路径。

于 2013-03-29T17:50:48.763 回答