#### 回顾 动态规划/`DFS`(深度优先搜索)/回溯 算法框架

借用二叉树来回顾一下之前学习的 动态规划/DFS(深度优先搜索)/回溯 三种框架：

动态规划框架：

//自顶向下递归的动态规划
int dp(状态1,状态2,...){
    for(选择 in 所有可能的选择){
        //状态因为选择发生改变
        result = 求最值(result,dp(状态1,状态2,...))
    }
    return result;
}
//自底向上迭代的动态规划
dp[0][0][...] = base case;
//进行状态转移
for 状态1 in 状态1 的所有取值{
    for 状态2 in 状态2 的所有取值{
        for...{
            dp[状态1][状态2][...] = 求最值(选择1，选择2，...);
        }
    }
}

动态规划的本质是将问题分解为多个子问题，找出最优子结构，得出状态转移方程，最后递推出结果。

[!TIP]

重叠子问题、最优子结构、状态转移方程 动态规划三要素

DFS(深度优先搜索) 与回溯框架：

//多叉树节点
class Node{
    int key;
    int val;
    Node[] children; 
}

//DFS 算法把[做选择][撤销选择]的逻辑放在for循环外面
void dfs(TreeNode root){
    if(root == null) return;
    //做选择
    System.out.println("进入%s节点",root.key);
    for(TreeNode child:root.children){
        dfs(child);
    }
    //撤销选择
    System.out.println("退出%s节点",root.key);
}

//回溯算法把[选择][撤销选择]的逻辑放在for循环里面
void backtrack(TreeNode root){
    if(root == null) return;
    for(TreeNode child:root.children){
        //做选择
        System.out.println("站在从%s节点到%s节点的树枝上",root.key,child.key);
        backtrack(child);
        //撤销选择
        System.out.println("将要离开从%s节点到%s节点的树枝",child.key,root.key);
    }
}

[!IMPORTANT]

• 动态规划属于分解问题的思路，着重点在于每棵子树。
• DFS算法属于遍历的思路，着重点在于每个节点。
• 回溯算法属于遍历的思路，着重点在于每个树枝。

BFS(广度优先搜索) 算法详解

**BFS**的核心思想：把一些问题抽象成图，从一个点开始，向四周扩散。BFS 算法一般都会借助队列来遍历图中的所有节点，每遍历到一个新节点，就把与这个节点相连的其他结点加入到队列之中。Dijkstra 算法就是典型的例子。

BFS 与 DFS 的核心区别在于：BFS找到的路径一定是最短的，但代价就是空间复杂度可能比DFS大很多，从后文的代码框架就很容易看出来了。

BFS算法框架

在介绍框架之前，我们先了解一下BFS算法使用最多的场景，**问题的本质就是让你在一个图中找到【start】到终点【target】的最短路径，这个例子听起来枯燥，但其实BFS算法都在干这个事 **，把这个本质弄清楚了，解决经过包装的各种问题才能得心应手嘛。

这个广义的描述可以有各种变体:

• 比如走迷宫，有的格子是围墙，那么从起点到终点的最短距离是多少？如果有的格子会有传送门【实施瞬间传送】呢，最短距离又是多少？
• 再比如说两个单词，要求你通过某些替换，每次替换可以增加、删除或替换一个字符，最少要替换几次呢？（这个在动态规划系列里提到过，dp[i][j]表示word1[0...i] 转换到word2[0...j]所需要的最少操作数）
• 再比如连连看游戏，两个方块消除的条件不仅是图案相同，还得保证两个方块之间的最短连线不能超过两个拐点。玩连连的时候，游戏是如何判断最短连线不超过两个拐点的呢？

变体有很多，但本质就是在一个【图】中，找【start】到【target】的最短路径罢了，只是加了一些限制条件。

BFS框架：

int BFS(Node start, Node target){
    queue<Node> q; //存储接下里要遍历的节点
    set<Node> visited; //存储已经遍历过的节点

    q.push(start);
    visited.insert(start);
    int step = 0;

    //开始广度优先搜索
    while(!q.empty()){
        //遍历这一层的节点
        int num = q.size(); 
        for(int i = 1;i <= num;i++){
            step++;
            Node cur = q.front();
            q.pop();
            if(cur == target){
                return step;
            }
            //如果此节点不是目标节点，则将此节点的邻接节点推入队列，继续访问下一个节点
            for(Node x:cur.adj()){
                if(visited.count(x) == 0){
                    q.push(x);
                    visited.insert(x);
                }
            }
        }
    }
    //走到这里说明已经遍历完图中的所有节点，表明图中没有target
}

队列q 为BFS的核心数据结构，cur.adj()泛指当前节点cur的所有邻接节点，如果这个图我们用邻接表的形式存储的话，cur.adj()其实就是节点cur对应的邻接链表，类似的在二维数组中，cur上下左右四面的位置就是相邻节点，也就是邻接节点。visited的主要作用是为了防止走回头路，已经遍历过的节点就不要再遍历了，这对于大部分可回头的问题是必须的，但是对于二叉树这种（没有子节点指向父节点的指针）是不需要的。

二叉树的最小高度(LeetCode111)

我们通过 判断二叉树的最小高度 这道题来实践一下BFS框架。

---

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

**说明：**叶子节点是指没有子节点的节点。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：2

示例 2：

输入：root = [2,null,3,null,4,null,5,null,6]
输出：5

提示：

• 树中节点数的范围在 [0, 105] 内
• -1000 <= Node.val <= 1000

---

怎么套BFS框架呢，简单分析后不难发现，这道题的root根节点 和 最靠近root根节点的叶子节点 就是BFS框架里的【start】与【target】。

if(cur.left == null && cur.right == null){
    //一检测到叶子节点，立马结束
    做出相应操作并结束程序，返回结果
}

现在我们只要对BFS框架稍加改造，即可得出结果：

int BFS(Node start){
    queue<Node> q; //存储接下里要遍历的节点
    set<Node> visited; //存储已经遍历过的节点

    q.push(start);
    visited.insert(start);
    int level = 0; //记录层数

    //开始广度优先搜索
    while(!q.empty()){
        level++;
        //遍历这一层的节点
        int num = q.size(); 
        for(int i = 1;i <= num;i++){
            Node cur = q.front();
            q.pop();
            //找到叶子节点，返回当前遍历层数即可
            if(cur.left == null && cur.right == null){
                return level;
            }
            /*//如果此节点不是目标节点，则将此节点的邻接节点推入队列，继续访问下一个节点
            for(Node x:cur.adj()){
                if(visited.count(x) == 0){
                    q.push(x);
                    visited.insert(x);
                }
            }*/
            if(cur.left != null){
                q.push(cur.left);
            }
            if(cur.right != null){
                q.push(cur.right);
            } 
        }
    }
    //走到这里说明已经遍历完图中的所有节点，表明图中没有target
}

这里注意for循环与while的配合，while循环控制一层一层往下走，for循环利用num变量从左到右遍历每一层二叉树节点：

这一点非常重要，这个形式在BFS问题中非常常见，但是在 Dijkstra 算法模板框架 中我们修改了这种代码模式，读完并理解本文后你可以去看看 BFS 算法是如何演变成 Dijkstra 算法在加权图中寻找最短路径的。

话说回来，二叉树本身是很简单的数据结构，我想上述代码你应该可以理解的，其实其他复杂问题都是这个框架的变形，再探讨复杂问题之前，我们解答两个问题：

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

首先，看BFS的逻辑，level每增加一步，队列中的所有节点都往前迈一步(队列中存的是一层一层的节点)，这保证了第一次到达【target】时的步数是最小的。！！！BFS只是找到了最短路径的长度（从【start】到【target】的最少步数而已）。

如果想找到最短路径的整个路径，即最短路径经过了哪些节点，需要从【target】开始回溯，拿这个【求二叉树的最小深度】举例，我们从终点【target】开始回溯，依着父节点找，一直找到【start】，这条路径就是我们要找的最短路径。

其实DFS也能找到最短路径，只是DFS需要遍历所有的分支，遍历完才能得出最短的路径，而且DFS是依靠递归堆栈来记录走过的路径，这些缺点大大增加了时间复杂度，而BFS借助队列一次实行【齐头并进】，不用遍历完树的所有节点就可找到最短距离。

形象地说，DFS是线，BFS时面，DFS单打独斗，一个节点就往深处走，BFS是集体行动，一层遍历完了之后再进入下一层。

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

BFS虽然可以找到最短距离，但是空间复杂度较大，而DFS所需要的空间复杂度就比较小。

还是拿刚刚的【二叉树最小深度】举例，在最坏情况下，BFS的空间复杂度为最后一层的节点个数，也就是N/2,用Big O 表示的话也就是

O(N)O(N)O(N),而DFS的空间复杂度也就是递归堆栈所占空间，最坏情况下为O(logN)O(logN)O(logN)。

一般来说，一般在寻找最短路径的时候用BFS，其他时候还是用DFS

---

LeetCode752 打开转盘锁

你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以自由旋转：例如把 '9' 变为 '0'，'0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。

锁的初始数字为 '0000' ，一个代表四个拨轮的数字的字符串。

列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。

字符串 target 代表可以解锁的数字，你需要给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 -1 。

示例 1:

输入：deadends = ["0201","0101","0102","1212","2002"], target = "0202"
输出：6
解释：
可能的移动序列为 "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202"。
注意 "0000" -> "0001" -> "0002" -> "0102" -> "0202" 这样的序列是不能解锁的，
因为当拨动到 "0102" 时这个锁就会被锁定。

示例 2:

输入: deadends = ["8888"], target = "0009"
输出：1
解释：把最后一位反向旋转一次即可 "0000" -> "0009"。

示例 3:

输入: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
输出：-1
解释：无法旋转到目标数字且不被锁定。

提示：

• 1 <= deadends.length <= 500
• deadends[i].length == 4
• target.length == 4
• target 不在 deadends 之中
• target 和 deadends[i] 仅由若干位数字组成

---

这道题的密码锁和我们行李箱上的密码锁很类似，如果没有deadends限制的话，我们直接向着密码拨动就行了【第一个位置的数字转换成密码对应位置的数字需要几步 + … + 最后一个位置的数字转换成密码对应位置的数字需要几步】。

但是现在有了deadends这个限制条件，也就是说不能直接拨过去，可能需要绕一段路，这又该如何计算最少步数【最短距离】呢？

第一步，我们不管target与deadends限制条件，就思考一个问题，该怎么设计一个算法穷举所有可能的密码组合？

穷举呗，再贴合题目一点，如果只转一下锁，有多少种可能？很显然，有八种。四个位置，每个位置可以向上转，也可以向下转，总共八种可能。

比如从初始密码状态‘0000’开始，经过一次转锁操作，可以转成‘1000’,’9000’,’0100’,’0900’…等八种密码状态，再以这八种密码状态为基础，每个状态又可以延伸为另外八种状态。

仔细想想，这个问题就可以抽象为图的问题，每个节点有八个邻接节点，又让你求最短距离，这不就是典型的**BFS框架**吗，我们先写一个适应这个问题的简陋的【先不考虑限制条件和target】的BFS框架：

//将s[j]向上拨一格
string plusOne(string s,int j){
    //将字符串转换成字符数组进行操作，方便对单个字符进行处理
    char res[s.length()];
    strcpy(res, s.c_str());
    if(res[j] == '9'){
        res[j] = '0';
    }else{
        res[j] += 1;
    }
    string result(res);
    return result;
}
//将s[j]向下拨一格
String minusOne(string s,int j){
    //将字符串转换成字符数组进行操作，方便对单个字符进行处理
    char res[s.length()];
    strcpy(res, s.c_str());
    if(res[j] == '0'){
        res[j] = '9';
    }else{
        res[j] -= 1;
    }
    string result(res);
    return result;
}

//BFS框架，打印出所有密码
void BFS(String target){
    queue<string> q;
    q.push('0000');

    while(!q.empty()){
        int sz = q.size();
        for(int i = 1;i < sz;i++){
            string cur = q.front();
            q.pop();
            //输出遍历的所有节点
            cout << cur << endl;

            //将cur的相邻节点加入到队列里
            for(int j = 0;j < 4;j++){
                string up = plusOne(cur, j);
                string down = minusOne(cur, j);
                q.push(up);
                q.push(down);
            }
        }
        /*在这里增加步数*/
    }
    return; // 结束BFS遍历
}

这段代码可以遍历所有密码组合，但是仍然不能解决问题，有以下问题还没解决：

1. 会走回头路，比如说我们从‘0000’拨到‘1000’,但是从队列中拿出‘1000’时，可能还会拨出‘0000’，这样的话会产生死循环，我们需要建立一个visited集合。
2. 没有终止要求，按照要求，遍历到【target】时就要结束遍历并返回拨动的次数。
3. 没有对deadends的处理，按道理这些【死亡密码】是不能出现的，也就是说你遇到这些密码时需要跳过。

只要稍作修改就可得出最终代码：

//将cur[j]向上拨一格
string plusOne_(string cur, int j) {
    if (cur[j] == '9') cur[j] = '0';
    else cur[j] += 1;
    return cur;
}

//将cur[j]向下拨一格
string minusOne_(string cur, int j) {
    if (cur[j] == '0') cur[j] = '9';
    else cur[j] -= 1;
    return cur;
}

//将问题抽象成图的问题，利用BFS算法解决问题
int openLock(vector <string> &deadends, string target) {
    //需要先将死亡数字存储起来，为保证查找的时间复杂度为o(1),我们利用集合（哈希表）进行存储
    unordered_set <string> deads;
    for (string s: deadends) {
        deads.insert(s);
    }
    //记录穷举过的密码，防止走回头路
    unordered_set <string> visited;
    int step = 0;
    queue <string> q;
    q.push("0000");
    visited.insert("0000");
    //开始BFS遍历
    while (!q.empty()) {
        int sz = q.size();
        for (int i = 1; i <= sz; i++) {
            string cur = q.front();
            q.pop();
            //判断特殊情况和结束条件】
            if (deads.count(cur) != 0) {
                continue;
            }
            if (cur == target) {
                return step;
            }
            //将相邻的八个节点加入到q中
            for (int j = 0; j < 4; j++) {
                string plusOne = plusOne_(cur, j);
                if(visited.count(plusOne) == 0) {
                    q.push(plusOne);
                    visited.insert(plusOne);
                }
                string minusOne = minusOne_(cur, j);
                if(visited.count(minusOne) == 0) {
                    q.push(minusOne);
                    visited.insert(minusOne);
                }
            }
        }
        step++;
    }
    //走到这里已经遍历完连通图的所有节点了，说明没有target
    return -1;
}

其实这段代码还可以进行小小优化，既然集合visited的元素和集合deads里的元素都不让访问，那么直接将deads里的元素初始化进visited即可。

原文链接: https://juejin.cn/post/7380194029873741860

文章标签

后端开发程序员