algorithm - 如何判断两个人是否有联系

Question

问题是:

假设两个人在一个社交网站上注册，如何判断他们是否连接？

我的分析(阅读更多之后):实际上，问题是寻找 - 图中从 A 到 B 的最短路径。我认为 BFS 和 Dijkstra 的算法在这里都有效并且时间复杂度完全相同(O(V + E))因为它是一个未加权的图，所以我们不能利用优先级队列。所以，一个简单的队列就可以解决这个问题。但是，它们都没有解决问题:找到它们之间的路径。

此时，Bidrectrol 应该是更好的解决方案。

Answer 1

要找到两者之间的路径，您应该从广度优先搜索开始。首先找到A的所有邻居，然后找到A所有邻居的所有邻居，等等。一旦B被命中，你不仅有从 A 到 B 的路径，但您也有一个最短这样的路径。

Dijkstra's algorithm岩石，您可以通过从两端工作来加快速度，即找到 A 的邻居和 B 的邻居，并进行比较。

如果您进行深度优先搜索，那么您一次只能走一条路径。这会慢很多。