查找树中两个顶点之间的简单路径(无向简单图) [英] Finding simple path between two vertices in a tree (undirected simple graph)

问题描述

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

Given two vertices (A and B) and a tree (G) (undirected simple graph) - Find the vertices in the simple path between A and B in G. The algorithm should run in O(V) complexity.

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

for instance - find the vertices in the simple path between a and b:

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

答案应该是:k

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

I have tried to modify BFS to accomplish the goal but it doesn't seem to work so far.

有什么建议吗?

推荐答案

如果发现距离后问题是在重建路径，请按以下方式调整BFS:从要连接的两个顶点之一开始，做一个BFS.对于发现的每个顶点v，存储其前任:如果通过边线u->w发现顶点w，则w的前任为u.之后，可以从目标顶点开始，从前一个顶点到另一个前一个顶点，直到到达源顶点为止，然后以相反的顺序重建路径.

If the problem is reconstructing the path after you found the distance, adjust the BFS in the following manner: start at one of the two vertices you want to connect, do a BFS. For every vertex v you discover, store its predecessor: if you discover vertex w via the edge u->w, then the predecessor of w is u. You can afterwards reconstruct the path in reverse order by starting at the target vertex and going from predecessor to predecessor until you reach the source vertex.

示例:

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

如果计算从D到I的路径，则您具有以下前身:

If you calculate the path from D to I, then you have the following predecessors:

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

您还将有一些前辈不在您的道路上，因此它们在重建过程中不会有任何问题.在该示例中，您还将拥有

You'll also have some predecessors that don't lie on your path, so they won't matter during reconstruction. In the example, you'll also have

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

但是对于从BFS源D到目标I的路径，您在重建期间不会遇到它们.

but for a path from the source of the BFS D to the target I you won't meet them during reconstruction.

重构从I开始的路径时，先得到I<-G，然后得到I<-G<-F，依此类推，直到获得具有相反顺序的完整路径.

When you reconstruct the path starting at I, you get I<-G, then I<-G<-F, and so on until you have the full path in reverse order.

如果您只关心到一个目标的路径，则一旦发现目标，就可以中止BFS；但是，这不会改变复杂性.但是，如果您要从一个源顶点到所有目标的路径，请执行完整的BFS；否则，请执行完整的BFS.如果这样做，那么前任版本将允许您重构到任何目标顶点的路径.

If you only care about the path to one target, you can abort the BFS once you discovered the target; this won't change the complexity though. If however you want the paths to all targets from one source vertex, do the full BFS; if you do that, the predecessors will allow you to reconstruct the path to any target vertex.

这篇关于查找树中两个顶点之间的简单路径(无向简单图)的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！