algorithm - FB 配置文件连接

Question

我试图寻找我面试中一个问题的答案。但是没有解决办法。谁能帮我解决这个问题。这是问题描述:

给定两个人的名字 A 和 B。你知道他们都存在于 FB 上。你必须告诉他们之间是否有任何连接。如果存在连通性，那么您必须说出连通性的确切路径。通过连通性，他们的意思是 B 可以是 C 的 friend ，而 C 是 A 的 friend 。这样，A 和 B 之间就建立了连接，路径为 A -> B-> C

Answer 1

您可以使用 Bidirectional search .

主要思想:

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 表示为 A 组和 B 组中的人。

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

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