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

Question

我读过很多关于如何使用广度优先搜索、dfs、a*等的stackoverflow问题，问题是什么是最佳使用，以及如何在真实和模拟图形中实现它。E、 g

假设你有一个Twitter/Facebook/Some social networking site的社交图，在我看来，搜索算法的工作原理如下：

如果用户A有10个朋友，那么其中一个有2个朋友，另外3个朋友。搜索首先要找出用户A的朋友是谁，然后必须查找10个用户中的每个人的朋友。对我来说这好像是bfs？在

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

谢谢

Answer 1

对于我来说，如果你只是想遍历整个图，你使用什么算法并不重要，只要它只命中每个节点一次。当你注意到这一点时，你似乎是这么说的：

I'm just trying to traverse the whole graph

这意味着你的术语在技术上是有缺陷的——你说的是行走一个图，而不是搜索一个图。除非你真的在寻找某个特别的东西，而你似乎根本没有在问题中提到。在

也就是说，Facebook和Twitter是非常不同的图形结构，它们确实会对你的走路方式产生影响：

1. Facebook基本上是一个无向图。如果X是Y的朋友，Y必须是X的朋友（或与X有关系，或有亲属关系等）。

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

这些问题将对图的行走算法产生重大影响。老实说，如果你只想访问所有的节点，你甚至需要一个图吗？为什么不迭代所有这些呢？如果某些数据结构中的所有节点都是iterable，则可以使用如下生成器表达式：

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

显然，您需要调整nodeGenerator的内部结构来处理实际访问节点的方式。也就是说，大多数图结构实现了一个节点迭代器。然后，您可以随时通过以下方式创建迭代器：

^{pr2}$

也许我只是漏掉了问题的重点，但是现在你提出了一个关于搜索算法的问题，而不是一个搜索问题。由于优化和搜索的No Free Lunch特性，任何搜索算法的价值都将完全取决于您要检查的搜索问题。在

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

Answer 2

我在facebook上有大约300个朋友，我的一些朋友平均也有300个朋友。如果你想从中画出一张图，那将会是巨大的。纠正我，如果我错了。BFS在这种情况下会要求很高吗？在

谢谢 J