社交图广度优先搜索的 Python 使用

Question

我已经阅读了很多关于如何使用广度优先搜索、dfs、A* 等的 stackoverflow 问题，问题是什么是最佳用法以及如何在现实与模拟图中实现它。例如

假设您有 Twitter/Facebook/某些社交网站的社交图谱，在我看来，搜索算法的工作方式如下:

如果用户 A 有 10 个 friend ，那么其中一个有 2 个 friend ，另一个有 3 个。搜索将首先找出用户 A 的 friend 是谁，然后它必须查找这 10 个用户中每个人的 friend 是谁.对我来说，这就像男朋友？

但是，我不确定这是否是实现算法的方式。

谢谢，

Answer 1

我的两分钱，如果你只是想遍历整个图，那么你使用什么算法并不重要，只要它只命中每个节点一次。这似乎是你在注意时所说的:

I'm just trying to traverse the whole graph

这意味着您的术语在技术上存在缺陷 - 您是在谈论遍历图表，而不是搜索图表。除非您实际上是在尝试搜索特定的东西，而您似乎根本没有在问题中提及。

话虽如此，Facebook 和 Twitter 是非常不同的图形结构，它们确实会影响您如何浏览它们:

1. Facebook 从根本上说是一个无向图。如果 X 是 Y 的 friend ，则 Y 必须是 X 的 friend 。(或者有关系，或有关联等)。

2. Twitter 从根本上说是一个有向图。如果 X 跟随 Y，则 Y 不必跟随 X。

这些问题将显着影响图形行走算法。老实说，如果你只是想访问所有的节点，你还需要一张图吗？为什么不遍历所有这些呢？如果你有一些可迭代的数据结构 MY_DATA 中的所有节点，你可以有一个像这样的生成器表达式:

def nodeGenerator(MY_DATA)
    for node in MY_DATA:
        yield node

显然，您需要调整 nodeGenerator 内部结构以处理您实际访问节点的方式。话虽如此，大多数图形结构都实现了节点迭代器。然后你可以随时通过以下方式创建一个迭代器:

 for node in nodeGenerator(MY_DATA):
     (Do something here)

也许我在这里忽略了问题的重点，但目前您提出了一个关于搜索算法的问题，但没有搜索问题。由于 No Free Lunch优化和搜索的本质，任何搜索算法的值(value)将完全取决于您试图检查的搜索问题。

即使在同一数据集中也是如此。毕竟，如果您要搜索名字以字母 D 开头的每个人，一个很好的方法是按字母顺序对每个人进行排序并进行二分查找。相反，如果您试图找到每个人与凯文培根的分离程度，您将需要从培根先生开始并递归迭代所有认识他的人和他们认识的每个人的算法。这些都是你可以在 Facebook 或 Twitter 上做的事情，但如果没有任何细节，就真的没有办法推荐算法。因此，如果您什么都不知道，只需将每个人都作为列表进行迭代。它和其他任何东西一样好。如果您随后想要优化，请缓存所有计算。