algorithm - Size of a queue for BFS in a grid

Question

I want to run a BFS in a square grid of size N*N. There is a single starting node. I can only move up/down/left/right (not in diagonal). There may be obstacles in the grid.

Of course I want to use a queue to store the nodes I have to visit. It will be implemented as circular array of size S (fixed size). What is the minimum size for my array? I don't want it to overflow, even in the worst possible case.

A similar problem would be : given a node in a grid, what is the maximum number of node at exactly distance K from the starting node (for any 0 < K < 2*N)?

I think it would be hard to find an exact answer to this problem so a good approximation would be enough.

See this example (the rightmost picture) :

This is not a grid but we could make grid with the same pattern (where the white represents obstacles and the black fractal are the walkable nodes). We can see that we have a lot of nodes at EXACTLY the same distance from the node in the center (actually this number doubles everytime time a path splits in two). So I would like to know how large this number could get, and if there are other configurations that yields to the same situation.

To make it very clear my question is : can this number get LARGER than 2*N where N is the size of the N*N square grid.

Answer 1

是的，我认为这个数字可以变得更大，使用您提供的第三张图片应该很容易可视化。

想象一下，您只从该图的左上角四分之一开始。这将 N 定义为左上角四分之一的大小，并将 E 定义为与中心单元具有相同距离的端点的数量。

现在假设您要将网格扩展到完整的图形。这意味着您的 Nnew 现在是 2N（即长度增加了一倍，宽度也增加了一倍）。然而，端点 E 的数量现在增加了四倍（即 Enew = 4N），如图所示。

换句话说，随着 N 的增加，端点数量的增长速度比 N 快得多，因此对于足够大的 N，端点的数量必然会超过 2*N。

Answer 2

2*N如果我正确理解您的问题，由于障碍物的存在，节点与起始节点的最大距离可能为 > ：

. . . * . . .
. * . * . * .
. * . * . * .
. * . * . * .
. * . . . * .
. . * * * . .
. . A * B . . 

如果我数对了，从 A 到 B 的距离是 30，比 2*7 大得多。

如果没有障碍物，很容易计算边缘的最大尺寸，这将是一个简单的菱形边缘K（或与网格重叠的部分），因此具有最大尺寸2*N。

如上例所示，障碍物可以增加两个节点之间最短路径的长度。他们可以增加最大可能的边缘尺寸吗？我不能很快想出一个他们这样做的例子，我怀疑他们不能，但我也想不出一个快速的证明。

Answer 3

可能是因为您想知道队列的最大大小而想知道距离 K 处的单元格数量吗？

如果是这样，为什么不直接使用基于列表的循环缓冲区（或者，或者，使用数组并在缓冲区满后自己重新分配一个更大的缓冲区）？

这完全跳过了您的问题，并且列表调整大小行为不应该成为问题：如果空间不足，大多数实现会将底层数组的大小加倍，因此无论如何您不应获得超过 O(log n) 的重新分配。