查找树中两个顶点之间的简单路径（无向简单图）

  • Z时代
  • 2024-01-10
  • 分类：问答

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

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

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

答案应该是：k

我试图修改BFS以实现该目标，但到目前为止似乎还行不通。

有什么建议？

回答：

如果发现距离后问题在于重构路径，请按以下方式调整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。但是，这不会改变复杂性。但是，如果要从一个源顶点到所有目标的路径，请执行完整的BFS；如果这样做，那么前任版本将允许您重构到任何目标顶点的路径。

以上是 查找树中两个顶点之间的简单路径（无向简单图） 的全部内容， 来源链接： utcz.com/qa/432149.html

回到顶部