如何確定兩個節點是否是同一棵樹/圖的一部分？

Question

我在面試中被問到這個問題，以確定兩個人是否直接或間接連接在Facebook上。說一個有幾個朋友b，c，d，e和c有幾個朋友b，d，f，g和f有朋友x，y，z。那麼a和z是間接的朋友。

有沒有一個很好的算法來找出它們是如何連接的？

This後有類似的問題，但他有太多的標準，所以我認爲必須有一個更好的方式來做到這一點。任何人都可以建議嗎？

Answer 1

運行Breadth First Search以獲得到達該特定朋友的最小躍點數，如果可達的話。通過在目前訪問的節點上保留一些書籍，您可以讓遍歷的朋友到達正在搜索的朋友。

該算法運行在班輪時間O(V + E)。

僞代碼：

廣度優先搜索（圖，根，目標）：如果需要找到朋友之前，參觀了朋友正在搜索

create empty set Checked 
create empty queue Queue  

add Root to Checked 
Queue.enqueue(Root)      

while Queue is not empty { 
    Current = Queue.dequeue() 
    if Current.has(Goal) { 
     return Current 
    } 
    for each Node that is adjacent to Current { 
     if Node is not in Checked { 
      Checked.add(Node) 
      Queue.enqueue(Node) 
     } 
    } 
} 

是大於1你可以說他們是間接連接的。

這也可以用來檢查它們是否連接。