Python在社交图中的广度优先搜索使用方法
我最近在看很多关于如何使用广度优先搜索、深度优先搜索、A*算法等的StackOverflow问题。我的疑问是，什么情况下使用这些算法最合适，以及在实际应用中如何实现它们，而不是仅仅在模拟图上使用。例如：
想象一下你有一个社交网络图，比如Twitter、Facebook或者其他社交网站。对我来说，搜索算法的工作方式大概是这样的：
假设用户A有10个朋友，其中一个朋友有2个朋友，另一个朋友有3个朋友。搜索算法首先会找出用户A的朋友，然后再查找这10个朋友各自的朋友。对我来说，这听起来像是广度优先搜索（bfs）？
不过，我不确定这是否是实现这个算法的正确方法。
谢谢！
2 个回答
我在Facebook上大约有300个朋友，而我的一些朋友平均也有300个朋友。如果你要把这些关系画成一个图，那这个图会非常庞大。请纠正我，如果我说错了的话？在这种情况下，使用广度优先搜索（BFS）会不会很费劲呢？
谢谢，J
我觉得，如果你只是想遍历整个图，使用什么算法其实没那么重要，只要每个节点只访问一次就行。你提到的：
我只是想遍历整个图
这说明你的用词有点问题——你是在说走访图，而不是搜索图。除非你实际上是想找某个特定的东西，但在你的问题中似乎并没有提到这一点。
说到这里，Facebook和Twitter的图结构是非常不同的，这会影响你如何走访它们：
Facebook本质上是一个无向图。如果X是Y的朋友，Y也必须是X的朋友。（或者是恋爱关系，或者是亲戚等等）。
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)
也许我没理解你的问题，但目前你提出了一个关于搜索算法的问题，却没有一个搜索问题。由于优化和搜索的无免费午餐原则，任何搜索算法的价值完全取决于你想要解决的搜索问题。
即使在同一个数据集里也是如此。毕竟，如果你在找所有名字以字母D开头的人，一个很好的方法是把所有人按字母顺序排序，然后进行二分搜索。如果你想找每个人与凯文·贝肯的关系程度，你就需要一个从贝肯先生开始的算法，递归遍历认识他的人以及他们认识的人。这两种情况你都可以在Facebook或Twitter上做到，但没有具体细节，真的很难推荐一个算法。因此，如果你什么都不知道，直接把每个人当作一个列表遍历就行了。这和其他方法一样好。如果你想要优化，可以缓存任何计算结果。