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

Question

我正在尝试了解BFS解决方案的空间复杂性，以解决“编程面试的元素”中的布尔矩阵问题。它类似于Leetcode中的洪水填充问题（问题733）。

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

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

Answer 1

[在任何时间点，队列都不能包含两个节点u和v，以使distance(start, u)和distance(start, v)相差大于1。假设为论证，u与起始节点是3，v的距离是5：

如果v出现在队列中的u之前，那么我们将在u之前访问它-这是一个矛盾，因为BFS在较远距离的节点之前访问较早距离的节点。

如果u出现在队列中的v之前，那么当我们访问u时，我们会将u的邻居添加到队列中。这些邻居离起始节点的距离为4，但是它们现在在队列中的[[after v中，因此，尽管距离大于4，v仍将在它们之前被访问-另一个矛盾。

因此，始终存在一定距离d，因此队列仅包含距离d或距离d + 1的节点，此外，距离d的所有节点都出现在距离d + 1的任何节点之前在队列中。这是BFS算法的loop invariant。

在2D网格中，对于任何d > 0，距起点距离d的节点数最多为4*d，因此队列的最大可能大小为4*d + 4*(d + 1)。同样，M乘N网格中任意两个节点之间的最大距离为M + N - 1。因此，O(M + N)在任何时候都是队列大小的渐近界限。