为何网格BFS的空间复杂度常被记为O(m*n)，实测却显示为O(m+n)？

你之前的实测结论没有问题，也不存在逻辑遗漏，核心误区其实是很多人对BFS队列的存储范围有误解：队列不会存所有已经遍历过的节点，只会存当前等待处理的那一层节点，一旦节点出队完成邻接遍历，就会被永久移出队列，不会再占队列空间。

不同起点对应的最大队列规模规律 #

你的猜想完全可以被严格推导验证：

• 从网格四个角落出发时，最大队列规模确实是 O(min(m, n))。以左上角(0,0)起点为例，BFS每一层都是和起点曼哈顿距离相等的斜向单元格集合，这个层的宽度会从1开始逐步增长，直到斜向带碰到网格的右边界或下边界时达到峰值，峰值长度等于网格的短边长度，之后就会逐步收窄，整体规模和短边正相关。
• 从网格中心位置出发时，最大队列规模确实是 O(m + n)。中心起点的等距离层是一个不断向外扩大的正菱形结构，当菱形的四条边刚好顶到网格的上下左右四个边界时，层的宽度达到峰值。比如200行200列的网格，中心位置起点扩展到这个阶段时，单条斜边上的节点数是100，四条边去重交叉点后的总节点数刚好是399，和你测试得到的最高队列值完全对应。
• 未知起点的最坏场景下，空间复杂度上限就是 O(m + n)，不存在更高的可能。

为什么队列规模永远不会达到 O(m*n)？ #

同一个BFS层内的所有节点，到起点的曼哈顿距离完全相等，这类节点在网格上永远是一条斜向的带状结构，不可能铺满整个 m*n 的平面区域。最极端的情况，当带状结构刚好横跨整个网格的横向、纵向边界时，宽度也只有 m + n 的量级，远小于网格总节点数 m*n。
比如1行1000列的超长条网格，不管从哪个点出发做BFS，队列的最大尺寸永远不会超过2，和总节点数1000完全不在一个量级，更能说明队列规模和总节点数没有正比关系。

你的测试程序测得的线性增长规律、和 m+n 成正比的结果，完全符合理论推导，没有逻辑漏洞。

内容的提问来源于stack exchange，提问作者ValarMorghulis