BFS知识点总结

文章目录

• BFS执行过程
• BFS思考过程
• 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/