理解空间复杂度 - BFS 解决方案 - 绘制布尔矩阵

Question

我试图理解“编程面试要素”中绘制布尔矩阵问题的 BFS 解决方案的空间复杂度。它类似于Leetcode中的Flood fill问题（问题733）。

解决方案是这样的。我可以将需要更改的当前元素添加到队列中。任何相邻（顶部/底部/向上/向下）节点也需要更改。所以我将它们添加到队列中（如果它们满足添加到队列的条件。每当处理队列中的元素时，都会添加其相邻元素。我们将进行处理，直到队列不为空。

我认为空间复杂度（最坏情况）将为 O(MN)，因为所有元素也可能在队列中。但书中提到，最坏情况的空间复杂度是 O(M+N)，因为距节点给定距离最多有 O(M+N) 个条目。我知道元素也会不断地从队列中删除。即使如此，我也很难想象他们是如何达到这种空间复杂性的。有人可以帮我理解吗？

Answer 1

关键是 BFS 按照距起始节点的距离远近的顺序来访问节点。这就是 BFS 适合在未加权图中查找最短路径的原因。

\n\n

在任何时间点，队列都不能包含两个节点u和v且distance(start, u)相差distance(start, v)超过 1。为了论证起见，假设u与起始节点的距离为 3，且v的距离为 5：

\n\n

\n
• 如果在队列中v发生在之前，那么我们就在之前访问它- 这是一个矛盾，因为 BFS 在访问距离较远的节点之前访问距离较早的节点。uu
\n
• 如果u出现v在队列之前，那么当我们访问 时u，我们会将u\ 的邻居添加到队列中。这些邻居距起始节点的距离为 4，但它们现在在队列中位于后面 ，因此尽管距离大于 4，但仍会在它们之前被访问 - 另一个矛盾。vv
\n

\n\n

因此，在任何时候，都存在一定的距离d，使得队列仅包含距离为d或距离 的节点d + 1，并且此外，距离为的所有节点都出现在队列中d距离为距离的任何节点之前。d + 1这是BFS 算法的循环不变量。

\n\n\n\n

假设您正在 M×N 网格上执行 BFS，其中每个节点都连接到其所有正交邻居。那么对于任意一个，距起始点d > 0距离最大的节点数为，因此队列的最大可能大小为。另外，任意两个节点之间的最大距离为。因此，O(M + N) 是任意时刻队列大小的渐近界限。d4*d4*d + 4*(d + 1)M + N - 1

\n\n

在网格中的某些节点“缺失”的情况下（即被洪水填充的区域的颜色错误），最大距离是 O(MN) 而不是 O(M + N)；所以这个案子要困难得多。直觉是，如果图具有较长的路径，那么用于分支路径的“开放”空间就会较少，从而导致队列较小。在极端情况下，图可以是一条长路径，但在这种情况下队列的大小为 O(1)。

\n\n

然而，有些图表4*d超出了界限，因此队列可能更大。例如，可以构造如下形式的图，其中图大小为 O(2 ^k ) 但队列大小达到 O(3 ^k )，因此 BFS 的空间复杂度为 \xce\x98((M + N ) ^{log ₂ 3} ) 在这组图上。因此，所引用的 O(M + N) 空间复杂度在最坏情况下并不成立，但可能在平均情况下成立。

\n\n

\n\n

该图像由 Heap Overflow 制作（发布在评论中）；起始节点为黄色，红色节点将同时进入队列。

\n