我想在N * N大小的正方形网格中运行BFS。有一个单独的起始节点。我只能向上/向下/向左/向右移动（而不是对角线）。 电网中可能存在障碍物。网格中BFS队列的大小
当然，我想用一个队列来存储我必须访问的节点。它将被实现为大小为S（固定大小）的圆形数组。我的阵列的最小尺寸是多少？即使在最坏的情况下，我也不希望它溢出。
一个类似的问题是：给定网格中的一个节点，在距离起始节点确切距离K处的节点的最大数量是多少（对于任何0 < K < 2 * N）？
我认为很难找到这个问题的确切答案，所以一个好的近似就足够了。
见这个例子中（最右边的图片）：
这不是一个网格，但我们可以使格栅具有相同的模式（其中白色代表的障碍和黑色的分形是步行的节点）。我们可以看到，我们有很多节点在确切地说是与中心节点的距离相同（实际上这个数字在每次路径分裂为两倍的时候加倍）。 所以我想知道这个数字有多大，以及是否有其他配置可以产生相同的情况。
为了弄清楚我的问题是：这个数字可以大于2 * N，其中N是N * N正方形网格的大小。
难道你想知道距离K处的单元数，因为你想知道队列的最大尺寸吗？
如果是这样，为什么不直接使用基于列表的循环缓冲区（或者，也可以使用数组，并在缓冲区满后自行重新分配更大的缓冲区）？
这完全跳过了你的问题，列表大小调整行为不应该是一个问题：大多数实现将底层数组的大小加倍，如果它们用尽空间，所以你不应该超过O（log n ）无论如何重新分配。
是的，这正是我想要计算我的数组大小的原因。除了我知道我可以使用链表或可调整大小的数组。我只问，因为我对答案感兴趣。 – user1637030
如果我正确理解你的问题，从起始节点的节点的最大距离可能是>2*N因为障碍物的存在：
. . . * . . .
. * . * . * .
. * . * . * .
. * . * . * .
. * . . . * .
. . * * * . .
. . A * B . .
如果我算正确，距离从A到B是30，这比2 * 7多得多。
如果不是障碍物，很容易计算边缘的最大尺寸，这将是边缘K（或与网格重叠的部分）的简单菱形，因此最大尺寸2*N。
如上例所示，障碍物可以增加两个节点之间最短路径的长度。他们可以增加最大可能的条纹尺寸吗？我不能很快想出一个他们做的例子，我怀疑他们做不到，但我也想不到一个快速的证明。
我不想计算2个节点之间的最大距离，而是计算一定距离处的最大节点数。 – user1637030
@ user1637030，我明白了。但是你问，“距离起始节点正好距离K处的节点的最大数量是多少（对于任何0
是的，我认为这个数字可以变得更大，并且使用您提供的第三张图像 进行可视化应该很容易。
想象一下，您只能从该图的左上角开始。这将N定义为该左上角四分之一的大小，E表示与中心单元具有相同距离的所有端点的数量。
现在想象一下，你想扩大你的网格到完整的数字。这意味着你的Nnew现在是2N（即长度增加了一倍，宽度也增加了）。然而，终点E的数目现在增加了四倍（即Enew = 4N），如图所示。
换句话说，当N增加，终端数量的增长大于N快得多，因此 端点的数量势必超过2 * N为一个足够大的N.
你可以通过一个网格中的同一个节点更多一次，直到你必须清空你的队列？如果不是，在最坏的情况下，你可以运行整个网格，或N^2个位置。否则，有什么限制，因为你可能需要停止一段时间？ – Rubens
这是一个BFS，因此每个节点只会添加（并弹出）一次。我不能同时拥有N * N个职位。 – user1637030
我很抱歉，但我并没有真正解决问题。你有一个网格，NxN，从给定的角度来说，你执行一个BFS。网格中确定节点的子节点是什么？他们的邻居没有被视为兄弟姐妹？有什么障碍？在3x3的网格中，如果您从网格中最左边的最顶端节点开始，那么您的搜索跨度如何？你能举个例子吗？ – Rubens