我想在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