查找樹中兩個頂點之間的簡單路徑（無向簡單圖）

Question

給定兩個頂點（A和B）和一棵樹（G）（無向簡單圖） - 在A和B之間的簡單路徑中查找頂點G. 該算法應該以O（V）複雜度運行。

例如 - 發現A和B之間的簡單路徑的頂點：

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

答案應該是：克

我試圖修改BFS來完成目標，但它不」 t似乎迄今爲止工作。

有什麼建議嗎？

Answer 1

如果問題在找到距離後重建路徑，請按以下方式調整BFS：從要連接的兩個頂點之一開始，執行BFS。對於您發現的每個頂點v，存儲其前任：如果您通過邊緣u->w發現頂點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;如果你這樣做，前輩們將允許你重建任何目標頂點的路徑。