algorithm - 寻找树中两个顶点之间的简单路径(无向简单图)

Question

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

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

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

答案应该是:k

我曾尝试修改 BFS 以实现目标，但到目前为止它似乎不起作用。

有什么建议吗？

Answer 1

如果问题是在找到距离后重建路径，请按以下方式调整 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；如果这样做，前辈们将允许您重建到任何目标顶点的路径。