有一个图最多有10000个节点，每个节点最多可以有4个相邻节点。图是未加权和无向。任务是找到从节点 A 到节点 B 的最短路径。路径长度是路径中访问的节点数. BFS 算法能否在 1 秒 内找到该路径并使用小于 64mB 的内存？
原来的问题是网格(最大100*100)和可以访问的地方，开始的地方，结束的地方，不能访问的地方。我的第一个猜测是将其简化为使用 BFS 搜索在未加权图中找到最短路径。但是，我不确定该解决方案在处理大图时的速度和内存使用情况。
最佳答案
空间复杂度
所以你有 10000 个节点，每个节点最多可以连接 4 个其他节点。最大顶点数为 40 000。在 adjency list 中它需要 O(|V|+|E|)=50 000 内存空间。每个变量都需要 32 位来在列表中表示它。最大内存量为 40000*32/(1000*1000*8)=0.16 兆字节。如果adjacent matrix使用它需要 O(|V|^2)=40000*40000/(1000*1000*8)=200 兆字节。
时间复杂度
维基百科:
The time complexity can be expressed as O(|V|+|E|) since every vertex and every edge will be explored in the worst case. Note: O(|E|) may vary between O(|V|) and O(|V|^2), depending on how sparse the input graph is (assuming that the graph is connected).
所以在最坏的情况下，时间复杂度将是 O(|V|+|E|) = 40 000 + 10 000 = 50 000。使用现代计算机，在 1 秒内完成计算不是问题。
关于algorithm - BFS 搜索最短路径的性能，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15327960/