我试图寻找我面试中一个问题的答案。但是没有解决办法。谁能帮我解决这个问题。这是问题描述:
给定两个人的名字 A 和 B。你知道他们都存在于 FB 上。你必须告诉他们之间是否有任何连接。如果存在连通性,那么您必须说出连通性的确切路径。 通过连通性,他们的意思是 B 可以是 C 的 friend ,而 C 是 A 的 friend 。这样,A 和 B 之间就建立了连接,路径为 A -> B-> C
最佳答案
您可以使用 Bidirectional search .
主要思想:
AGroup = {A},BGroup = {B}。
while intersect(AGroup,BGroup) = 空集:
2.1 展开AGroup中还没有展开的每个人并将结果插入AGroup。
2.2 展开 BGroup 中尚未展开的每个人并插入结果 BGroup。
2.3 如果AGroup和BGroup没有变化,返回“A和B没有连接”。
将 S 表示为 A 组和 B 组中的人。
现在您有了从 A 到 S 的路径,以及从 B 到 S 的路径。
返回 A->...->S->...->B。
关于algorithm - FB 配置文件连接,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/11682830/