Last renew: October 13, 2022 pm

Breadth First Search - 广度优先搜索

BFS的核心思想

把一些问题抽象成图，从一个点开始，向四周开始扩散。所以一般来说我们写BFS都是用队列这种数据结构，每次将一个节点周围的所有节点加入队列。

BFS与DFS的区别

BFS找到的路径一定是最短的，但代价就是空间复杂度很高。

为什么BFS可以找到最短路径，DFS不行吗？

DFS实际上是靠递归的对栈记录走过的路径，你要找到最短路径就得把二叉树中所有树杈都探索完，才能对比出来。时间复杂度会很高。但BFS可以借助队列做到一次一步，齐头并进，是可以在不遍历完整树的条件下找到最短距离的。

既然BFS那么好，为啥DFS还存在？

DFS的空间复杂度较低。

处理二叉树的例子，假如是个满二叉树，节点数为N，对于DFS算法来说，空间复杂度无非就是递归对栈，最坏情况树的高度O(logN)

但对于BFS算法，队列中每次都会储存着二叉树一层的节点，这样最坏情况下空间复杂度应该是树的最底层节点的数量N/2，那就是O(N)

由此观之，一般在找最短路径用BFS，其他时候DFS多一些。

BFS出现的常见场景

问题的本质就是让你在一幅「图」中找到从起点start到终点target的最短距离。

BFS的基础框架

int BFS(Node start, Node target) {
    Queue<Node> q; // 核心数据结构
    Set<Node> visited; // 避免走回头路
    
    q.offer(start); // 将起点加入队列
    visited.add(start);
    int step = 0; // 记录扩散的步数

    while (q not empty) {
        int sz = q.size();
        /* 将当前队列中的所有节点向四周扩散 */
        for (int i = 0; i < sz; i++) {
            Node cur = q.poll();
            /* 划重点：这里判断是否到达终点 */
            if (cur is target)
                return step;
            /* 将 cur 的相邻节点加入队列 */
            for (Node x : cur.adj()) {
                if (x not in visited) {
                    q.offer(x);
                    visited.add(x);
                }
            }
        }
        /* 划重点：更新步数在这里 */
        step++;
    }
}

BFS的基础思路

用Queue储存每次的路径。

用HashSet储存访问过的节点（命名为visited）以防走回头路。

注：遍历二叉树等不存在回头路的情况时，不需要考虑visited储存的方式。

注2: 遍历二叉树时，一般可以用while控制深度，用for控制广度。for完一层，while下一层，这样的逻辑。

BFS刷题清单

LC112

在基础的bfs上，用一个队列记录每个节点的累加值，这样就避免了值的过度累计（因为每层只需要一个但遍历了所有，不好实现）

LC117

大致思路依旧是在bfs框架上做操作。节点操作思路是先设置一个前置节点，让前置节点连接cur，然后再将他所连接的cur变成后置节点。

LC200

不能死板的卡在原有的bfs模版上，说白了bfs就是一种暴力的遍历罢了。对于这道题来说，先遍历所有的1，然后找到1之后对其做有限界的bfs，然后修改数组/用一个boolean数组记录。直到遍历所有的。

顺带学到了一种对于二维数组的bfs框架方法：

Queue<Integer> neighbors = new LinkedList<>();
// 用r*n+c进行记录 r是row c是column。然后求除/或者取余就行。
neighbors.offer(r * n + c);
while (!neighbors.isEmpty()) {
    int id = neighbors.poll();
    int row = id / n;
    int col = id % n;
    if (row - 1 >= 0 && grid[row-1][col] == '1') {
       neighbors.offer((row-1)*n + col);
       grid[row-1][col] = '0';
    }
    if (row + 1 < m && grid[row+1][col] == '1') {
       neighbors.offer((row+1)*n + col);
       grid[row+1][col] = '0';
    }
    if (col - 1 >= 0 && grid[row][col-1] == '1') {
       neighbors.offer(row*n + col - 1);
       grid[row][col-1] = '0';
    }
    if (col + 1 < n && grid[row][col+1] == '1') {
       neighbors.offer(row*n + col + 1);
       grid[row][col+1] = '0';
    }

LC207

拓扑排序(Topological ordering)：一个有向无环图(DAG, Directed Acyclic Graph)的所有顶点的线性序列。且该序列满足：

每个顶点出现且只出现一次
若存在一条从顶点A到顶点B的路径，那么在序列中顶点A出现在顶点B的前面。

注：只要这个图是DAG，那么他至少有一条拓扑排序。相反，我们也可以利用他是否有拓扑排序来验证该图是否有环。

这个题蛮有意思，可以用BFS也可以用DFS。我先用BFS做一下。

思路很重要。我们只要能够证明遍历完整张图我都无法找到一条拓扑排序，就能代表这张图不是DAG。反之，只要能够找到任意一条，就能证明这张图是DAG。

那么遍历方式可以利用BFS。

首先，将所有初始入度为0的节点放入队列中（若没有的话直接false，因为有环）。
然后取出队列中的节点，逐一消除掉与他相关的边（即将与这个节点相连的节点的入度-1）
在这个过程中如果有新的节点的度数为0，则将新的节点加入队列当中。循环直到队列中没有节点，并且在这个过程中计算节点数。
判断遍历过的节点数。如果所有节点都被遍历完成，代表我们找到了一条拓扑排序。

时间复杂度：O(N+M)最坏情况就是遍历完所有节点和所有边，然后节点数为N，边数为M。

空间复杂度：利用了一个ArrayList<ArrayList<Integer>>结构，外层的arraylist是N个节点，里层的是M条边。所以依旧是O(N+M)

LC301

很有意思的题，虽然是道hard，但本质其实就是一道easy+一道medium。首先你要会判断一个包含括号的字符串是否valid，然后可以利用BFS/回溯+剪枝完成一个遍历。

遍历方式是每轮删除一个括号，然后存到set中。之后遍历Set判断，合法的就存，不合法的就扔。删除字符串的方式也蛮有趣，选择了子字符串+子字符串。

LC399

Programming

Use Django to Develop Web Application Previous

Breadth First Search-广度优先搜索