如何修改 BFS 算法以便在图非常大的情况下找到从 A 到 B 的最短路径？

Question

我所指的“非常大的图”是每个顶点都有1000个相邻顶点，但如果您查看最终解决方案，则从 A 到 B 的距离仅为 6（假设）。

在这种情况下，使用基本的 BFS 算法将是浪费的，因为它会将 A 的所有1000个相邻顶点放在第一轮中，然后在下一轮中放置这些顶点的每个1000个相邻顶点，如此类推... 当我到达 B 时，我已经考虑了 1000^6 个顶点。

有何优化方法？或者说，是否有一种方法可以进行优化？

- Pradhan

Answer 1

一种简单的方法是双向工作：

在每个步骤中，执行以下操作：

• 获取寻找B的nbrsA的新邻居，如果未找到，则设置nbrsA = new neighbors
• 获取寻找A的nbrsB的新邻居，如果未找到，则设置nbrsB = new neighbors
• 比较nbrsA和nbrsB

如果图形很大但高度连接，则通过这种方式可以节省相当多的空间，但比较邻居集合需要花费一些额外时间。

- PengOne

Answer 2

你可以将BFS改为使用Dijkstra算法。BFS和Dijkstra在某些方面是相关的，因此这种修改应该是可接受的。而且由于这是一次电话面试，他们很可能希望你看到它们之间的关系。

- grdvnl

---

Dijkstra算法适用于带权图。否则，它就变成了BFS。我猜楼主讨论的是无权图。 - dagnelies

Dijkstra算法适用于无权图。在处理过程中，您只需将所有路径的权重设置为“1”即可。 或者，您可以将1000个相邻的边压缩成一条权重为1000的单独边。（尽管在最后这一点上，我觉得问题有点模糊。） - john_science

Answer 3

我同意，

这是一个有趣的问题。据我所见，有两个方法可能对您有所帮助：

1. 同时向前和向后搜索。如果您确实有1000的最小度数，则在BFS的d次迭代中需要调查1000^d个节点。这有效地将1000^(2d)减少为2*1000^d。

2. BFS在某一点变得过于昂贵以至于内存消耗。为了避免这种情况，您可以切换到“迭代加深”：通过进行深度优先搜索（仅限于1次迭代）来模拟BFS，然后进行DFS（限制为2次迭代），以此类推。开销是一个小常数（当然不理想），但这样您就可以避免内存问题，同时以与BFS相同的顺序发现节点。

- Michael Nett

Answer 4

有两种可能性：

这1000个顶点经常被共享，这意味着一旦它们在第一轮中被找到，它们将在第二轮中被忽略，从而大大降低了您的搜索范围，

或者

这1000个顶点是唯一的，这意味着您有数百万或数十亿个节点，这意味着您仍处于算法预期的规模。

无论哪种方式，都没有太多事情可做。

- corsiKa

---

我希望我能使用这个答案，我刚刚完成了一个电话面试，而这正是他们问我的问题。我给出的一些建议是，尝试走到六级，然后考虑下一个相邻的顶点。虽然不是最好的想法，但也算是更好的。 - Pradhan

说实话，这是一个非常糟糕的面试问题。他们要求你改进计算机科学中最基本和广泛使用的算法之一。很有可能他们拥有一个形式不良的数据结构，只是想从聪明人那里得到好的想法，而没有意识到他们的根本问题，或者他们发现了一些聪明的边角案例，并将其用作预期的答案。无论哪种方式，他们都不是你想为之工作的人。BFS将在O(n)中找到路径...你做得没什么更多的事情了！如果你的n很大，那么你的n就很大...抱歉！ - corsiKa