BFS知識點總結

文章目錄

• BFS執行過程
• BFS思考過程
• • 1.狀态表示
  • 2.狀态轉移
  • 3.狀态存儲
• BFS常用模闆（C++版）
• BFS常見題型總結

BFS執行過程

BFS思考過程

1.狀态表示

判斷題目中有幾個變量在不斷變化，這些不斷變化的變量就是我們要找的狀态。

2.狀态轉移

通常開一個多元數組（根據狀态個數來表示，有幾個狀态就開幾維）, 根據題目的要求先将這些狀态偏移量儲存在狀态數組中，友善轉移

3.狀态存儲

将這些轉移後的狀态存儲在隊列中，友善下一次轉移。

BFS常用模闆（C++版）

queue<int> q;
st[0] = true; // 表示1号點已經被周遊過
q.push(0);

while (q.size())
{
    int t = q.front();
    q.pop();

    for (int i = h[t]; i != -1; i = ne[i])
    {
        int j = e[i];
        if (!st[j])
        {
            st[j] = true; // 表示點j已經被周遊過
            q.push(j);
        }
    }
}
           

BFS常見題型總結

算法應用

一般的BFS算法可分為兩種：

（1）每個元素為一個狀态，比如走迷宮問題狀态轉換是下一步往哪走。bfs相對于與dfs可以找到走迷宮的一個最短路徑（按層周遊時第一次到達終點時即為最短路徑）

（2）每個整體為一個狀态，比如八數位問題狀态轉換是下一步整體是往哪個狀态變。

參考： https://www.acwing.com/blog/content/1864/