algorithm - FB 配置文件连接

Question

我试图寻找我面试的一个问题的答案。但没有得到解决。任何人都可以帮助我解决这个问题。下面是问题描述：

给定两个人的名字 A 和 B。你知道两者都存在于 FB 上。你必须告诉他们之间是否有任何联系。如果存在连通性，那么您必须说出连通性的确切路径。通过连通性，他们的意思是 B 可能是 C 的朋友，而 C 是 A 的朋友。通过这种方式，A 和 B 之间存在连接，路径将是 A -> B- > C

Answer 1

您可以使用双向搜索。

主要思想：

1. AGroup = {A}，BGroup = {B}。

2. while intersect(AGroup,BGroup) = 空集：

   2.1 展开 AGroup 中尚未展开的每个人，并将结果插入 AGroup。

   2.2 展开 BGroup 中尚未展开的每个人，并插入结果 BGroup。

   2.3 如果AGroup和BGroup没有变化，返回“A和B未连接”。

3. 将 S 表示为 AGroup 和 BGroup 中的人。

现在你有了从 A 到 S 的路径，以及从 B 到 S 的路径。

返回 A->...->S->...->B。