如何确定两个节点是否是同一棵树/图的一部分？

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你可以说他们是间接连接的。

这也可以用来检查它们是否连接。