algorithm - BFS 搜索最短路径的性能

Question

有一个最多包含10 000 个节点的图，每个节点最多可以有4 个相邻节点。图是未加权且无向的。任务是找到从节点A到节点B的最短路径。路径长度是路径中访问的节点数。BFS 算法能否在不到一秒的时间内找到该路径并使用少于64mB的内存？

最初的问题是网格（最大 100*100）和可以访问的地方、开始地点、结束地点和无法访问的地方。我的第一个猜测是使用 BFS 搜索将其减少为在未加权图中找到最短路径。但是，我不确定带有大图的解决方案的速度和内存使用情况。

Answer 1

空间复杂度

所以你有 10 000 个节点，每个节点最多可以连接 4 个其他节点。最大顶点数为 40 000。在邻接列表中，它需要O(|V|+|E|)=50 000内存空间。每个变量都需要 32 位才能在列表中表示它。最大内存量为40000*32/(1000*1000*8)=0.16MB。如果使用相邻矩阵，则需要O(|V|^2)=40000*40000/(1000*1000*8)=200Mbytes。

时间复杂度

维基百科：

时间复杂度可以表示为 O(|V|+|E|)，因为在最坏的情况下将探索每个顶点和每条边。注意：O(|E|) 可能在 O(|V|) 和 O(|V|^2) 之间变化，具体取决于输入图的稀疏程度（假设图是连接的）。

所以在最坏的情况下，时间复杂度将是O(|V|+|E|) = 40 000 + 10 000 = 50 000。使用现代计算机，在 1 秒内计算不会成为问题。

Answer 2

1s 是好的（在现代计算机上更像 0.001s -- 10^9 操作/秒）。

内存——你需要邻接表表示数组 int[10000][4] + 一些东西来记住关闭/使用/看不见的节点 >= 10000*4*6 = 240000 = 0.24MB。所以如果我的数学没问题应该没问题。