BFS算法题

目录

1.BFS

 2.树里的宽搜 

题目一——429. N 叉树的层序遍历 - 力扣（LeetCode）

 题目二——103. 二叉树的锯齿形层序遍历 - 力扣（LeetCode）

题目三——662. 二叉树最大宽度 - 力扣（LeetCode） 

题目四——515. 在每个树行中找最大值 - 力扣（LeetCode）

3.BFS解决最短路径问题 

为什么BFS可以解决最短路径问题

题目一——1926. 迷宫中离入口最近的出口 - 力扣（LeetCode）

题目二——433. 最小基因变化 - 力扣（LeetCode） 

 题目三——127. 单词接龙 - 力扣（LeetCode）

题目四——675. 为高尔夫比赛砍树 - 力扣（LeetCode） 

4.多源BFS

题目一——542. 01 矩阵 - 力扣（LeetCode）

题目二——1020. 飞地的数量 - 力扣（LeetCode）

题目三—— 1765. 地图中的最高点 - 力扣（LeetCode）

题目四—— 1162. 地图分析 - 力扣（LeetCode）

 5.BFS解决拓扑排序

题目一——207. 课程表 - 力扣（LeetCode）

题目二——210. 课程表 II - 力扣（LeetCode） 

---

 

1.BFS

BFS 全称是 Breadth First Search，中文名是宽度优先搜索，也叫广度优先搜索。

是图上最基础、最重要的搜索算法之一。

所谓宽度优先。就是每次都尝试访问同一层的节点。 如果同一层都访问完了，再访问下一层。

BFS广度优先搜索，在处理问题时，优先考虑更多的机会，而不是像DFS那样优先走一条路，再回溯

BFS基于队列实现，目的是把可能的解放在同一层处理，即BFS队列中至多只有两层的解

考虑完前一层可能的解后，再考虑下一层的解。把当前解的后续解再放到队列尾部。

BFS是基于队列实现的 

如上图中，BCDE处在同一层考虑，那么

1. 考虑到 B 的后续解FGH时，先把B弹出队列，再把FGH 放在 CDE 后面，即CDEFGH 。
2. 考虑到 C 的后续解IJ时，先把C弹出队列，再把 IJ 放在 DEFGH 后面，即 DEFGHIJ 。
3. 考虑到 D 的后续解K时，先把D弹出队列，再把 K 放在 EFGHIJ 后面，即 EFGHIJK 。
4. 考虑到 E 的后续解（这里没有）时，先把E弹出队列，再把这里就不需要放在 FGHIJK 后面了，即 FGHIJK 。

 现在队列里面只剩下第三层的了！！！这样子我们可以一直按照上面这个逻辑执行下去，直到队列为空

---

下面结合一个图 (graph) 的实例，说明 BFS 的工作过程和原理：

（1）将起始节点1放入队列中，标记为已遍历： 

（2）从queue中取出队列头的节点1，找出与节点1邻接的节点2,3，标记为已遍历，然后放入queue中。

 （3）从queue中取出队列头的节点2，找出与节点2邻接的节点1,4,5，由于节点1已遍历，排除；标记4,5为已遍历，然后放入queue中。

（4）从queue中取出队列头的节点3，找出与节点3邻接的节点1,6,7，由于节点1已遍历，排除；标记6,7为已遍历，然后放入queue中。

（5）从queue中取出队列头的节点4，找出与节点4邻接的节点2,8，2属于已遍历点，排除；因此标记节点8为已遍历，然后放入queue中。

（6）从queue中取出队列头的节点5，找出与节点5邻接的节点2,8，2,8均属于已遍历点，不作下一步操作。

（7）从queue中取出队列头的节点6，找出与节点6邻接的节点3,8,9，3,8属于已遍历点，排除；因此标记节点9为已遍历，然后放入queue中。

（8）从queue中取出队列头的节点7，找出与节点7邻接的节点3, 9，3,9属于已遍历点，不作下一步操作。

（9）从queue中取出队列头的节点8，找出与节点8邻接的节点4,5,6，4,5,6属于已遍历点，不作下一步操作。

（10）从queue中取出队列头的节点9，找出与节点9邻接的节点6,7，6,7属于已遍历点，不作下一步操作。

（11）queue 为空，则遍历结束

---

 2.树里的宽搜 

我们看一下怎么使用BFS遍历树？

如下动图所示：

下面解释一下整个 BFS 的过程，我们整个遍历的过程是这样的：

1、将节点 A 加入到队列 q 中。此时队列只有一个结点 A。

2、队列 q 不为空，我们弹出队列的首节点，也就是 A，找到 A 的所有邻接节点。从上图可以看出，也就是 B、C、D，我们将 B、C、D 加入到队列中。这样队列内的元素就是 B,C,D。

3、队列 q 不为空，我们弹出队列的首节点，也就是 B，找到 B 的所有邻接节点。从上图可以看出，也就是 E、F，我们将 E、F  加入到队列中。这样队列内的元素就是 C,D,E,F。

4、队列 q 不为空，我们弹出队列的首节点，也就是 C，找到 C 的所有邻接节点。从上图可以看出，C 没有邻接节点。这样队列内的元素就是 D,E,F。

5、队列 q 不为空，我们弹出队列的首节点，也就是 D，找到 D 的所有邻接节点。从上图可以看出，也就是 H、I、J，我们将 H、I、J 加入到队列中。这样队列内的元素就是 E,F,H,I,J。

6、队列 q 不为空，我们弹出队列的首节点，也就是 E，找到 E 的所有邻接节点。从上图可以看出，C 没有邻接节点。这样队列内的元素就是 F,H,I,J。

7、队列 q 不为空，我们弹出队列的首节点，也就是 F，找到 F 的所有邻接节点。从上图可以看出，F 没有邻接节点。这样队列内的元素就是 H,I,J。

8、队列 q 不为空，我们弹出队列的首节点，也就是 H，找到 H 的所有邻接节点。从上图可以看出，也就是 K，我们将 K 加入到队列中。这样队列内的元素就是 I,J,K。

9、队列 q 不为空，我们弹出队列的首节点，也就是 I，找到 I 的所有邻接节点。从上图可以看出，也就是 G、L，我们将 G、L 加入到队列中。这样队列内的元素就是 I,J,K,G,L。

10、队列 q 不为空，我们弹出队列的首节点，也就是 I，找到 I 的所有邻接节点。从上图可以看出，I 没有邻接节点。这样队列内的元素就是 J,K,G,L。

11、队列 q 不为空，我们弹出队列的首节点，也就是 J，找到 J 的所有邻接节点。从上图可以看出，J 没有邻接节点。这样队列内的元素就是 K,G,L。

12、队列 q 不为空，我们弹出队列的首节点，也就是 K，找到 K 的所有邻接节点。从上图可以看出，K 没有邻接节点。这样队列内的元素就是 G,L。

13、队列 q 不为空，我们弹出队列的首节点，也就是 G。从上图可以看出，G 没有邻接节点。这样队列内的元素就是 L。

14、队列 q 不为空，我们弹出队列的首节点，也就是 L。从上图可以看出，L 没有邻接节点。这样队列内就没有元素，结束。

题目一——429. N 叉树的层序遍历 - 力扣（LeetCode）

 

 这个题目的意思是相当简单易懂的吧。

有人可能好奇：为什么层序遍历需要借助队列这个数据结构呢？

我们看下面这个图就明白了

额，这个不是和那个队列的先进先出的性质是一模一样的吗？所以我们就借助队列来解决这种问题。

1. 我们先搞一个队列，如果根节点不为空，我们让根节点入队列
2. 接下来是一个while循环，当队列不为空的时候，一直执行下面这个
3. 先把队头元素从队列里删除，把队头元素的孩子入队。
4. 直到这个队列为空为止，这个层序遍历就算是结束了。

我们现在来考虑一下，我们怎么分层呢？

我们其实可以另外设置一个变量，先统计队列有多少个元素，有多少的元素，我们就先出队多少次。这个时候，队列里就只剩孩子结点了（即下一层的），然后我们重复上面这个步骤就好了。

我们很快就能写出下面这个代码啊！ 

class Solution {
public:vector<vector<int>> levelOrder(Node* root) {vector<vector<int>>ret;//记录最终结果queue<Node*>q;if(root==nullptr){return ret;}q.push(root);//将根结点添加进队列里面while(q.size()!=0){vector<int>tmp;//统计本层的元素int s=q.size();//记录当前队列里面的元素个数//先把队列里所有结点的孩子结点加入到队列里面for(int i=0;i<s;i++){Node* t=q.front();//获取队列第一个元素q.pop();//删除队列第一个元素tmp.push_back(t->val);//将队列第一个元素的值添加进tmp里面//将第一个元素的孩子结点添加进队列里面//注意孩子结点是以数组的方式访问的for(Node* child:t->children){if(child!=nullptr){q.push(child);}}}ret.push_back(tmp);//将本层的结果集添加进总的结果里面}return ret;}
};

 

 题目二——103. 二叉树的锯齿形层序遍历 - 力扣（LeetCode）

 

 这题和上面那题好像差不多，只不过就是改变了层序遍历的规则而已。

我们还是使用BFS来解决，我们增加一个标记位，这个锯齿形遍历就只需要在偶数行将结果逆序一下就好了。

class Solution 
{public:vector<vector<int>> zigzagLevelOrder(TreeNode* root) {vector<vector<int>>ret;//总的结果queue<TreeNode*> q;//队列if(root==nullptr){return ret;}q.push(root);//将根节点加入到队列里面int level=1;//每一行的标记位while(q.size()!=0){vector<int>tmp;//记录这一行的结果int sz=q.size();for(int i=0;i<sz;i++){TreeNode* f=q.front();//获取队列的第一个元素q.pop();//删除队列的第一个元素tmp.push_back(f->val);//将第一个元素添加进这一行的结果集里面if(f->left!=nullptr){q.push(f->left);}if(f->right!=nullptr){q.push(f->right);}}if(level%2==0)//偶数行的结果要逆置{reverse(tmp.begin(),tmp.end());}level++;//更新标记ret.push_back(tmp);}return ret;}};

题目三——662. 二叉树最大宽度 - 力扣（LeetCode） 

 

特别注意：这题是要将空结点来当作一个有效的元素的，这就让这一题没有那么简单了啊

---

我们可以利用数组存储二叉树的方式给结点编号，大家可以回忆一下堆的实现：堆的介绍，堆的向下调整算法，堆的向上调整算法_堆调整-CSDN博客

对于数组下标为1开始的情况，对于给定下标 i 的结点，其父结点、左子结点和右子结点的下标可以通过以下关系式计算：

• 下标i元素的左子结点下标：2 * i 
• 下标i元素的右子结点下标：2 * i + 1

• 还是利⽤层序遍历，但是这⼀次队列⾥⾯不单单存结点信息，并且还存储当前结点如果在数组中存 储所对应的下标（在我们学习数据结构-堆的时候，计算左右孩⼦的⽅式）。
• 这样我们计算每⼀层宽度的时候，⽆需考虑空节点，只需将当层结点的左右结点的下标相减再加 。

 但是，这⾥有个细节问题：

如果⼆叉树的层数⾮常恐怖的话，我们任何⼀种数据类型都不能存下下标 的值。

但是没有问题，因为

• 我们数据的存储是⼀个环形的结构；
• 并且题⽬说明，数据的范围在 int 这个类型的最⼤值的范围之内，因此不会超出⼀圈；

因此，如果是求差值的话，我们⽆需考虑溢出的情况。

class Solution {
public:// 计算给定二叉树的宽度int widthOfBinaryTree(TreeNode* root) {// 使用数组来模拟一个队列来存储节点和它们的相对位置（基于层级的编号）// TreeNode* 表示节点，unsigned int 表示该节点在其层级中的位置编号（从1开始）vector<pair<TreeNode*, unsigned int>> q; // 根节点入队，位置编号为1q.push_back({root, 1});// 用于存储最宽层的宽度unsigned int ret = 0;// 当队列不为空时，继续循环while (q.size()) {// 获取当前层最左边和最右边节点的位置编号// x1 和 y1 是当前层最左边的节点及其位置编号// x2 和 y2 是当前层最右边的节点及其位置编号auto& [x1, y1] = q[0];auto& [x2, y2] = q.back();// 更新最宽层的宽度为当前层最左边和最右边节点的位置编号之差加1ret = max(ret, y2 - y1 + 1);// 准备下一层的节点入队vector<pair<TreeNode*, unsigned int>> tmp; // 临时队列，用于存储下一层的节点// 遍历当前层的所有节点for (auto& [x, y] : q){// 如果左子节点存在，将其入队，位置编号为当前节点位置编号的两倍if (x->left)tmp.push_back({x->left, y * 2});// 如果右子节点存在，将其入队，位置编号为当前节点位置编号的两倍加一if (x->right)tmp.push_back({x->right, y * 2 + 1});}// 更新队列为下一层的节点q = tmp;}// 返回最宽层的宽度return ret;}
};

题目四——515. 在每个树行中找最大值 - 力扣（LeetCode）

这题一点难度也没有 

class Solution {
public:vector<int> largestValues(TreeNode* root) {vector<int> ret;queue<TreeNode*> q;if (root == nullptr) {return ret;}q.push(root);while (q.size() != 0) {int sz = q.size();int tmp = INT_MIN;for (int i = 0; i < sz; i++) {TreeNode* f = q.front();q.pop();tmp = max(tmp, f->val);if (f->left != nullptr) {q.push(f->left);}if (f->right != nullptr) {q.push(f->right);}}ret.push_back(tmp);}return ret;}
};

3.BFS解决最短路径问题 

这个最短路径其实是图论的问题，但是我们不讨论加权的情况，我们只考虑边权相同的情况

最短路径无非就是给你很多点，然后问你两个点的最短路径是多少！

这个解法特别简单，我们只需要从起点开始进行BFS即可。

然后我们需要一个哈希表来记录我们访问过的位置

我们把A放进队列里面，然后标记A为已经访问，然后看看A能访问哪些点，就是B,C，把这些点放进队列里面，然后标记B,C为可读，

1. 然后接着看B能访问哪些点，这里是D，然后把这个D放到这个队列里面来，然后弹出B
2. 然后接着看C能访问哪些点，这里是E，然后把这个E放到这个队列里面来，然后弹出C 

 后面发现D没必要另外拓展了，因为肯定比C的长。

……

为什么BFS可以解决最短路径问题

广度优先搜索（BFS）能够解决最短路径问题，尤其是在无权图（即图中所有边的权重都相等）的情况下。以下是BFS为何适用于解决最短路径问题的几个关键点：

1. 层次遍历：BFS按照层次（或深度）遍历图中的节点。它从起始节点开始，首先访问所有直接相连的邻居节点，然后再访问这些邻居节点的邻居，以此类推。这种层次遍历的方式保证了在访问到某个节点时，该节点是通过最短路径从起始节点到达的（在无权图中）。

2. 最短路径性质：在无权图中，任何节点到起始节点的最短路径都可以通过逐步向外扩展的方式找到。BFS正是按照这种方式进行遍历的，因此它能够在找到目标节点时保证是通过最短路径到达的。

3. 队列实现：BFS通常使用队列（FIFO，先进先出）来实现。起始节点被放入队列中，然后依次处理队列中的节点。对于每个节点，它的所有未访问过的邻居节点都会被加入到队列的末尾。这样，当队列中的某个节点被处理时，它一定是通过最短路径从起始节点到达的（因为队列中的节点是按照层次顺序排列的）。

4. 避免重复访问：为了确保算法的正确性，BFS需要跟踪已经访问过的节点，以避免重复访问和陷入无限循环。这通常通过一个布尔数组或集合来实现。

• 为什么使用BFS能解决最短路径问题

因为使用BFS时，我们都是让每种情况同时发生，保证每种情况每一次行走的步数都是一样的，这样子最先到达终点的情况一定是最短路径

如何找到最短路径是多少啊？

• 拓展的层数就是最短路径

题目一——1926. 迷宫中离入口最近的出口 - 力扣（LeetCode）

 

• 为什么使用BFS能解决最短路径问题

因为使用BFS时，我们都是让每种情况同时发生，每一次行走的步数都是一样的，这样子最先到达终点的情况一定是最短路径

我们完全可以假设这个人往上下左右四个方向同时走，每一次都走一步，这样子最先到达终点的就是最短路径

• 那我们怎么保证同时走呢？

很简单，我们还是使用层序遍历的那个思路，我们只需要保证每走一步的所有情况都处理完，才会去讨论下一步的情况！！！

• 我怎么知道哪些情况是同一步的啊？

我们其实可以另外设置一个变量，先统计队列有多少个元素，有多少的元素，我们就先出队多少次。这个时候，队列里就只剩下一步的，然后我们重复上面这个步骤就好了。

class Solution {
public:bool check[101][101]={false};int dx[4]={0,0,-1,1};int dy[4]={1,-1,0,0};int nearestExit(vector<vector<char>>& maze, vector<int>& entrance) {int i=entrance[0],j=entrance[1];check[i][j]=true;queue<pair<int,int>>q;q.push({i,j});int path=0;while(q.size()!=0){ path++;int sz=q.size();//同一步有多少种情况for(int s=0;s<sz;s++){//处理这一步的情况auto [a,b]=q.front();q.pop();//当前这一步处理完，才会考虑下一步for(int k=0;k<4;k++){int x=a+dx[k],y=b+dy[k];if(x>=0&&x<maze.size()&&y>=0&&y<maze[0].size()&&maze[x][y]=='.'&&check[x][y]==false){//是否已经到达出口了if(x==0||x==maze.size()-1||y==0||y==maze[0].size()-1){return path;}q.push({x,y});check[x][y]=true;}}}}return -1;}
};

题目二——433. 最小基因变化 - 力扣（LeetCode） 

 

 这个题目意思算是很简单了吧。

我们可以转换为边权为1的路径问题！！

我们可以从前往后遍历整个start字符串，从第一个位置开始 将它的每个位置都尝试修改成可以修改成的字符，如果说修改的字符串出现在bank里面并且这个字符串没有被出现过，我们就再次将它添加进这个队列里面

• 如果快速的将修改后的字符串和bank里面的进行配对？

答案是使用哈希表！！

这样子

class Solution 
{
public:int minMutation(string startGene, string endGene, vector<string>& bank) {unordered_set<string> vis; // 用于标记已经访问过的基因，防止重复搜索unordered_set<string> hash(bank.begin(), bank.end()); // 将基因库中的基因存储到哈希集合中，方便快速查找string change = "ACGT"; // 基因可能包含的字符集，用于生成所有可能的突变基因// 如果起始基因就是目标基因，则不需要任何突变if(startGene == endGene) return 0;// 如果目标基因不在基因库中，则无法找到路径if(!hash.count(endGene)) return -1;queue<string> q; // 使用队列进行广度优先搜索q.push(startGene); // 将起始基因加入队列vis.insert(startGene); // 标记起始基因为已访问int ret = 0; // 记录突变次数// 当队列不为空时，继续搜索while(q.size()){ret++; // 每遍历一层，突变次数加1int sz = q.size(); // 当前层的基因数量// 遍历当前层的所有基因while(sz--){string t = q.front(); // 取出当前基因q.pop(); // 从队列中移除当前基因// 对当前基因的每个位置进行突变尝试for(int i = 0; i < 8; i++) // 假设基因长度为8（这里需要根据实际情况调整）{string tmp = t; // 复制当前基因，用于尝试突变// 对当前位置进行四种可能的突变for(int j = 0; j < 4; j++){tmp[i] = change[j]; // 尝试将当前位置的字符替换为A、C、G、T之一// 如果突变后的基因在基因库中且未被访问过if(hash.count(tmp) && !vis.count(tmp)){// 如果找到了目标基因，返回当前的突变次数if(tmp == endGene) return ret;// 将突变后的基因加入队列，继续搜索q.push(tmp);// 标记突变后的基因为已访问vis.insert(tmp);}}}}}// 如果遍历完所有可能的路径都没有找到目标基因，则返回-1return -1;}
};

 题目三——127. 单词接龙 - 力扣（LeetCode）

 

 这题简直和上面那题是一模一样的。

class Solution {
public:int ladderLength(string beginWord, string endWord, vector<string>& wordList) {unordered_set<string> vis;unordered_set<string>hash(wordList.begin(),wordList.end());queue<string>q;q.push(beginWord);vis.insert(beginWord);int ret=1;//注意这里是从1开始的，最开始的那个单词也算while(q.size()!=0){ret++;int sz=q.size();while(sz--){string t=q.front();q.pop();for(int i=0;i<beginWord.size();i++){string tmp=t;for(char n='a';n<='z';n++){tmp[i]=n;if(hash.count(tmp)&&!vis.count(tmp)){if(tmp==endWord) return ret;q.push(tmp);vis.insert(tmp);}}}}}return 0;}
};

题目四——675. 为高尔夫比赛砍树 - 力扣（LeetCode） 

 

 

这个题目的意思必须得看懂啊！！！

从低向高砍树     这个必须得注意啊！！

这样子这个题目就有意思了啊，我们来解决一下

首先啊，我们得知道我们需要先获取这个砍树的顺序啊，我们可以遍历数组，把值大于1的保存到一个数组里面，然后对这个数组sort，就获取到了这个砍树的顺序。

然后我们就按照这个顺序去砍树啊，每次砍树时都调用BFS，计算从当前点去砍树点的最短步数是多少，每次寻找找一个砍树的点后就更新这个初始点，然后将这个步数累计起来，接下来重复之前的过程即可

class Solution {
public:int cutOffTree(vector<vector<int>>& forest) {//获取砍树的顺序vector<pair<int, int>> tree;for(int n=0;n<forest.size();n++){for(int i=0;i<forest[0].size();i++){if(forest[n][i]>1){tree.push_back({n,i});}}}sort(tree.begin(), tree.end(), [&](const pair<int, int>& p1, const 
pair<int, int>& p2){return forest[p1.first][p1.second] < forest[p2.first][p2.second];});// 2. 按照顺序砍树int bx = 0, by = 0;int ret = 0;for(auto& [a, b] : tree){int step = bfs(forest, bx, by, a, b);if(step == -1) return -1;ret += step;bx = a, by = b;}return ret;}int dx[4]={0,0,-1,1};int dy[4]={-1,1,0,0};bool vis[51][51];int bfs(vector<vector<int>>&forest,int i,int j,int bx,int by){if(bx == i && by == j) return 0;queue<pair<int,int>>q;memset(vis, false, sizeof(vis)); // 清空之前的数据q.push({i,j});vis[i][j] = true;int ret=0;while(q.size()!=0){ret++;int sz=q.size();while(sz--){auto [a,b]=q.front();q.pop();for(int k=0;k<4;k++){int x=a+dx[k],y=b+dy[k];if(x>=0&&x<forest.size()&&y>=0&&y<forest[0].size()&&forest[x][y]!=0&&vis[x][y]==false){if(x == bx && y == by) return ret;q.push({x,y});vis[x][y]=true;}}}}return -1;}
};

4.多源BFS

其实BFS有多源BFS和单源BFS。

多源BFS与单源BFS有什么区别呢？

• 单源BFS：从某一个点开始（起点）
• 多源BFS：从多个点同时开始走

如何解决多源BFS？

正常来说，在我们会了单源BFS的使用后，面对多个起点到一个终点的最短路问题也就是多源BFS，我们最先想到的就是暴力做法，也就是将多个起点分成一份份一个起点到一个终点的单源BFS问题，这样我们每个起点到终点的最短路都求出来再找最小值即可，但这种暴力几乎是一定超时的，最差时间复杂度都达到ON^3

一个一个起点算最短路会超时，那如果多个起点一块呢？

这时我们就发现，如果多个起点一块进行BFS搜索，重复的路程不再经过，这时不仅得出的答案正确，而且时间复杂度大大降低，这也就是多源BFS的核心思路，多个起点同时用单源BFS的方法去找最短路

核心代码几乎跟单源BFS一样，就是在最前面不是把一个起点加入队列，而是把多个起点全部加入队列

事实上多源的BFS，本质上与单源的BFS并无太大差别，我们只需要把多个起点等效成一个起点即可，这样就转化为了单源的问题了。

多源BFS：多个起点 ——> 多个起点同时加入队列！

核心：在求解多源BFS问题时，同时将所有起点加入队列即可！

 

注意：BFS只能解决边权为1的多源最短路问题 

题目一——542. 01 矩阵 - 力扣（LeetCode）

 

其实大家仔细看题目，题目就是想要我们把这个数组修改成该点到最近的0的路径！！ 

 对于求的最终结果，我们有两种⽅式：

1.  第⼀种⽅式：从每⼀个 1 开始，然后通过层序遍历找到离它最近的 0 。 这⼀种⽅式，我们会以所有的 1 起点，来⼀次层序遍历，势必会遍历到很多重复的点。并且如果 矩阵中只有⼀个 0 的话，每⼀次层序遍历都要遍历很多层，时间复杂度较⾼。
2. 换⼀种⽅式：从 0 开始层序遍历，并且记录遍历的层数。我们从0开始，去寻找最近的1。当第⼀次碰到 1 的时候，当前的层数 就是这个 1 离 0 的最短距离。 这⼀种⽅式，我们在遍历的时候标记⼀下处理过的 1 ，能够做到只⽤遍历整个矩阵⼀次，就能得 到最终结果。

但是，这⾥有⼀个问题， 0 是有很多个的，我们怎么才能保证遇到的 1 距离这⼀个 0 是最近的 呢？ 其实很简单，我们可以先把所有的 0 都放在队列中，把它们当成⼀个整体，每次把当前队列⾥⾯的所 有元素向外扩展⼀次。

class Solution {
public:// 更新矩阵函数，输入是一个二维整数矩阵，输出也是一个同样大小的二维整数矩阵// 输出矩阵中的每个元素表示从最近的零元素到该位置的最短距离vector<vector<int>> updateMatrix(vector<vector<int>>& mat) {int n = mat.size();       // 矩阵的行数int m = mat[0].size();    // 矩阵的列数// 创建一个与输入矩阵大小相同的距离矩阵，初始化为-1// -1 表示该位置尚未被搜索过// 非-1 值表示从最近的零元素到该位置的最短距离vector<vector<int>> distance(n, vector<int>(m, -1));// 创建一个队列用于广度优先搜索queue<pair<int, int>> q;// 首先，将所有为零的元素加入队列，并将它们在距离矩阵中的值设为0// 因为这些零元素本身就是最近的零元素，所以到它们自己的距离是0for (int i = 0; i < n; i++) {for (int w = 0; w < m; w++) {if (mat[i][w] == 0) {q.push({i, w});distance[i][w] = 0;}}}// 定义四个方向的行列偏移量，用于在矩阵中移动int dx[4] = {0, 0, -1, 1};  // 列偏移量：左移、右移不变、上移、下移int dy[4] = {-1, 1, 0, 0};  // 行偏移量：上移、下移不变、左移、右移// 广度优先搜索while (!q.empty()) {int sz = q.size();  // 当前队列中的元素数量，即当前层的节点数// 遍历当前层的所有节点for (int i = 0; i < sz; i++) {auto [a, b] = q.front();  // 获取队列前端的节点坐标q.pop();  // 弹出已处理的节点// 遍历当前节点的四个相邻节点for (int k = 0; k < 4; k++) {int x = a + dx[k];  // 计算相邻节点的行坐标int y = b + dy[k];  // 计算相邻节点的列坐标// 检查相邻节点是否在矩阵范围内且尚未被搜索过if (x >= 0 && x < n && y >= 0 && y < m && distance[x][y] == -1) {// 更新相邻节点在距离矩阵中的值// 当前节点到相邻节点的距离是当前节点到零元素的距离加1distance[x][y] = distance[a][b] + 1;// 将相邻节点加入队列，以便后续搜索q.push({x, y});}}}}// 返回更新后的距离矩阵return distance;}
};

distance[x][y] == -1时，我们必须知道这个mat[x][y]一定是1的。

因为这个mat[x][y]==0的情况，我们已经将distance[x][y]修改成0了

题目二——1020. 飞地的数量 - 力扣（LeetCode）

 

我们完全可以从边界开始往里面进行搜索，将可以搜索到的1进行标记一下，最后统计没有被标记的1即可。

修改数组元素版本

为了节约内存，我直接把可以到达边界的1全都修改成了-1 

class Solution {
public:// 计算完全被其他陆地包围的陆地的数量int numEnclaves(vector<vector<int>>& grid) {int n = grid.size();          // 获取网格的行数int m = grid[0].size();       // 获取网格的列数queue<pair<int,int>> q;       // 创建一个队列用于广度优先搜索（BFS）// 标记并加入边界上的陆地到队列中for (int i = 0; i < n; i++) {// 处理第一列if (grid[i][0] == 1) {grid[i][0] = -1;      // 标记为已访问q.push({i, 0});       // 加入队列进行BFS}// 处理最后一列if (grid[i][m-1] == 1) {grid[i][m-1] = -1;    // 标记为已访问q.push({i, m-1});     // 加入队列进行BFS}}// 处理第一行和最后一行for (int i = 0; i < m; i++) {// 处理第一行if (grid[0][i] == 1) {grid[0][i] = -1;      // 标记为已访问q.push({0, i});       // 加入队列进行BFS}// 处理最后一行if (grid[n-1][i] == 1) {grid[n-1][i] = -1;    // 标记为已访问q.push({n-1, i});     // 加入队列进行BFS}}// 定义四个方向的行列偏移量，用于在矩阵中移动int dx[4] = {0, 0, -1, 1};    // 列偏移量：左移、右移不变、上移、下移int dy[4] = {-1, 1, 0, 0};    // 行偏移量：上移、下移不变、左移、右移// 从边界上的陆地开始进行广度优先搜索（BFS）while (!q.empty()) {int sz = q.size();        // 当前层级的节点数量while (sz--) {auto [a, b] = q.front(); // 获取当前节点的坐标q.pop();                 // 从队列中移除当前节点// 遍历四个方向for (int k = 0; k < 4; k++) {int x = a + dx[k], y = b + dy[k]; // 计算新坐标// 检查新坐标是否在网格内且为陆地（值为1）if (x >= 0 && x < n && y >= 0 && y < m && grid[x][y] == 1) {grid[x][y] = -1; // 标记为已访问q.push({x, y});  // 加入队列进行下一轮BFS}}}}// 统计剩余的陆地（飞地）数量int ret = 0;for (int i = 0; i < n; i++) {for (int w = 0; w < m; w++) {if (grid[i][w] == 1) {ret++; // 统计飞地数量}}}return ret; // 返回飞地数量}
};

使用bool数组版本 

class Solution 
{// 定义四个方向的行列偏移量，用于在矩阵中移动int dx[4] = {0, 0, 1, -1}; // 列偏移量：左移、右移不变、上移、下移int dy[4] = {1, -1, 0, 0}; // 行偏移量：上移、下移不变、左移、右移public:// 计算完全被其他陆地包围的陆地的数量int numEnclaves(vector<vector<int>>& grid) {int m = grid.size();         // 获取网格的行数int n = grid[0].size();      // 获取网格的列数// 创建一个二维布尔数组，用于标记每个位置是否已被访问过vector<vector<bool>> vis(m, vector<bool>(n, false));// 创建一个队列用于广度优先搜索（BFS）queue<pair<int, int>> q;// 1. 将边上的陆地加入到队列中，并标记为已访问for (int i = 0; i < m; i++){for (int j = 0; j < n; j++){// 检查当前位置是否在网格的边上if (i == 0 || i == m - 1 || j == 0 || j == n - 1){// 如果边上的位置是陆地（值为1）if (grid[i][j] == 1){// 将该位置加入队列进行BFSq.push({i, j});// 标记该位置为已访问vis[i][j] = true;}}}}// 2. 进行多源BFS，从队列中取出陆地并标记其相邻的陆地while (!q.empty()){auto [a, b] = q.front(); // 获取当前陆地的坐标q.pop();                 // 从队列中移除当前陆地// 遍历四个方向for (int i = 0; i < 4; i++){int x = a + dx[i], y = b + dy[i]; // 计算相邻陆地的坐标// 检查相邻陆地是否在网格内、是陆地且未被访问过if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 && !vis[x][y]){// 标记相邻陆地为已访问vis[x][y] = true;// 将相邻陆地加入队列进行下一轮BFSq.push({x, y});}}}// 3. 统计结果：遍历整个网格，计算未被访问的陆地的数量int ret = 0;for (int i = 0; i < m; i++){for (int j = 0; j < n; j++){// 如果当前位置是陆地且未被访问过，则它是一个飞地if (grid[i][j] == 1 && !vis[i][j]){ret++; // 增加飞地的计数}}}return ret; // 返回飞地的数量}
};

 

题目三—— 1765. 地图中的最高点 - 力扣（LeetCode）

 

 我们应该从水域向外扩展。???这不就跟那个矩阵那题是一模一样的思路吗？

class Solution {// 定义四个方向的行列偏移量，用于在矩阵中移动int dx[4] = {0, 0, 1, -1}; // 列偏移量：左移、右移不变、上移、下移int dy[4] = {1, -1, 0, 0}; // 行偏移量：上移、下移不变、左移、右移
public:vector<vector<int>> highestPeak(vector<vector<int>>& isWater) {int n=isWater.size(),m=isWater[0].size();vector<vector<int>>ret(n,vector<int>(m,-1));queue<pair<int,int>>q;for(int i=0;i<n;i++){for(int w=0;w<m;w++){if(isWater[i][w]==1){q.push({i,w});ret[i][w]=0;}}}int step=0;while(q.size()!=0){step++;int sz=q.size();while(sz--){auto [a,b]=q.front();q.pop();for(int k=0;k<4;k++){int x=a+dx[k],y=b+dy[k];if(x>=0&&x<n&&y>=0&&y<m&&ret[x][y]==-1){ret[x][y]=ret[a][b]+1;q.push({x,y});}}}}return ret;}
};

题目四—— 1162. 地图分析 - 力扣（LeetCode）

 

嗯？仔细看一下题目，这不是01矩阵吗？

class Solution {// 定义四个方向的行列偏移量，用于在矩阵中移动int dx[4] = {0, 0, 1, -1}; // 列偏移量：左移、右移不变、上移、下移int dy[4] = {1, -1, 0, 0}; // 行偏移量：上移、下移不变、左移、右移
public:int maxDistance(vector<vector<int>>& grid) {int n=grid.size(),m=grid[0].size();vector<vector<int>> end(n,vector<int>(m,-1));queue<pair<int,int>>q;for(int i=0;i<n;i++){for(int w=0;w<m;w++){if(grid[i][w]==1){q.push({i,w});end[i][w]=0;}}}int path=0;int ret=-1;while(q.size()!=0){path++;int sz=q.size();while(sz--){auto [a,b]=q.front();q.pop();for(int k=0;k<4;k++){int x=a+dx[k],y=b+dy[k];if(x>=0&&x<n&&y>=0&&y<m&&end[x][y]==-1){end[x][y]=end[a][b]+1;q.push({x,y});ret=max(ret,path);}}}}return ret;}
};

 5.BFS解决拓扑排序

要知道什么拓扑排序我们首先要知道什么是有向无环图，有向无环图我们看名字其实就很容易理解，有向就是有方向，无环就是没有环形结构。

在图论中，如果一个有向图无法从某个顶点出发经过若干条边回到该点，则这个图是一个有向无环图（DAG图）。

有向无环图指的是有方向，但没有环的图。

图就是一个顶点和边连接而成的一个数据结构，有向图就是边都是有方向的。有向无环图就是图中是没有环的。如不能从1->2->3，3->2->4 所以这个图就是一个有向无环图。

如 4->5->6 是可以走通的，这就不是有向无环图了。

 

---

接下来我们来介绍一下有向图中的一些专业术语：

1. 入度（Indegree）：一个顶点的入度是指有多少条边指向这个顶点。换句话说，它表示该顶点有多少个直接前驱节点。（简单来说就是对于一个顶点来说，所有指向他的边之和）
2. 出度（Outdegree）：一个顶点的出度是指从这个顶点出发有多少条边。也就是说，它表示该顶点有多少个直接后继节点。（简单来说对于一个顶点来说，，这个顶点往外伸出的边的总和）

---

接下来我们来说说AOV网，也就是顶点活动图。

AOV网也叫做顶点活动图，它其实是一个有向无环的一个应用。

在有向无环图中，用顶点来表示一个活动，用边来表示执行活动的先后顺序的图结构

比如我想洗菜，我得先买菜，我想腌肉需要先买菜和准备厨具。。

---

3.拓扑排序

概念：略

大白话意思就是，在AOV网中找到做事情的先后顺序。

可以看到在这些活动中，其中一些活动必须在某些活动执行之后才能执行，比如说炒菜，必须先切菜，腌肉。所以在整个工程中这个炒菜绝对不可能先干。

 

那些活动可以先干呢？可以看到准备厨具、买菜可以先干，原因就是并没有边执行它们俩。可以先准备厨具，或者先买菜。所以从这里就可以发现一点，拓扑排序的结果可能不是唯一的！

如果先买菜，买完菜之后与买菜相连的箭头就可以删掉了，因为买完菜就可以解锁洗菜的操作了。所以这个箭头就可以删去了。。

 接下来可以准备厨具或者洗菜，原因是它俩都没有其他条件来限制。可以任选一个。

接下来只能洗菜。。。。。同理重复上面操作，最后我们就可以得到这样的做事情先后的序列，这也是就是拓扑排序的序列。找到做事情的先后顺序。

如何排序？

1. 找出图中入度为 0 的点，然后输出
2. 删除与该点相连的边
3. 重复1、2操作，直到图中没有点或者没有入度为 0 的点为止

图中没有点理解，所有活动都找完了可以停止了此时的序列就是拓扑排序的序列。

• 图中没有入度为 0 的点是怎么回事？

其实就是在这个拓扑排序中可能面对的不是有向无环图，是有环形结构的。

比如下面这个图，刚开始并不知道这个有向图是不是有环的，所以我们可以先做一下拓扑排序

当把1、3、2拿出来之后，发现剩下的都拿不出来了。原因就是4、5、6形成一个环路，是没有入度为0的边。

因此这个结束条件还需要加上直到图中没有入度为 0 的点为止 原因就是可能有环！

所以说拓扑排序有一个特别重要的应用，判断有向图中是否有环。

如何判断有向图中是否有环？

直接对图来一次拓扑排序，当拓扑排序过程中发现没有入度为0的点的时候，但是图中还有剩余点的时候，此时这个图中一定会有环形结构。

---

4.实现拓扑排序

借助队列，来一次 BFS 即可

初始化：把所有入度为 0 的点加入到队列中

当队列不为空的时候

1. 拿出队头元素，加入到最终结果中
2. 删除与该元素相连的边
3. 判断：与删除边相连的点，是否入度变成 0 ，如果入度为 0，加入到队列中

这里还有一个问题没说，如何建图？ 如何表示一个点的入度呢？下面的题在说。建完图然后搞拓扑排序。

题目一——207. 课程表 - 力扣（LeetCode）

 

 

其实这道题问题的就是有向图中是否有环。

我们可以把给的信息抽象称一张有向图，题目问能否完成所有课程学习意思就是能不能把这个课程排个序，说白了就是能否拓扑排序，能否拓扑排序也就是是否这个图是否是有向无环图 —> 有向图中是否有环？

做一次拓扑排序即可，前面已经说过如何拓扑排序，接下来重点就是如何建图？

如何建图？灵活使用语言提供的容器

看稠密（看数据量）

• 邻接矩阵（稠密图）
• 邻接表（稀疏图）

这道题我们用邻接表建图

相像中的邻接表最左边代表某个节点，这个节点右边一坨代表这个点所连接的点。

看起来就像一个个链表，头表示当前所考虑的这个节点，后面相连所有的节点是与我当前点相连的节点。我们建图的目的就是为了方便找到某个点所连接的那个点。不然还要遍历数组去找太麻烦了，所以把这些东西先存到一个数据结构中，这个数据结构就是图。

邻接表我们脑海中想到的应该就是这样的一条一条链表的结构。

 那如何实现一个邻接表呢？

我们没有必须真的搞一个链表出来，这里有两种方式：

1. vector<vector> edges
2. unordered_map<int,vector> edges

用vector嵌套一个vector是比较局限的，只能用于节点里面的值是数字表示的。

用unordered_map是比较万能的，可以把int —> string， vector< int > —> vector< string >，等等其他任何类型。

vector嵌套一个vector，通过下标可以找到与这个节点的值相连的其他节点。仅需在对应下标的vector做push_back就可以把与当前节点相连的节点加入。

用unordered_map就比较万能了，完全像刚才想象出来的邻接表结构，我们这里是一个int的数后面挂了一个int数组，那不就和一个节点挂着一个节点的效果一样的吗。用数组表示所连接的节点。

 

• 根据算法流程，灵活建图

刚才我们只是实现把所有的边存起来。我们还要根据算法流程多添加一些东西。

比如这里我们是做拓扑排序，因此我们需要直到每个顶点的入度是多少。可以搞一个vector< int > in，数组里面的值就表示这个顶点的入度是多少。

总结：建图先看数据量选择邻接矩阵还是邻接表来建图，然后根据算法流程，灵活的在建图的基础上多添加上一点东西。

class Solution {
public:bool canFinish(int n, vector<vector<int>>& prerequisites) {// 1. 准备工作unordered_map<int,vector<int>> edges;//邻接表存图vector<int> in(n);// 标记每一个顶点的入度// 2. 建图for(auto& e : prerequisites){int a = e[0], b = e[1];// b -> a 的一条边edges[b].push_back(a);// 把与b相连的顶点添加对应数组in[a]++;// 记录对应顶点的入度}// 3. 拓扑排序queue<int> q;// (1) 把所有入度为 0 的顶点加入到队列中for(int i = 0; i < n; ++i){if(in[i] == 0)q.push(i);}// (2) bfswhile(q.size()){int t = q.front();q.pop();//这道题没有让求顺序//把与这个顶点相连的边干掉,就是修改与其相连顶点的入度for(auto& a : edges[t]){in[a]--;//入度-1if(in[a] == 0)//入度变为0加入队列q.push(a);}}// 4.判断是否有环//如果整个拓扑排序结束之后,每个顶点的入度都变成0了说明没有环,否则就有环for(int i = 0; i < n; ++i){if(in[i]) return false;}return true;}
};

题目二——210. 课程表 II - 力扣（LeetCode） 

 

 

这道题和上面是一模一样的，还是做一次拓扑排序，不同的是这次要把拓扑排序顺序返回来。

class Solution {
public:vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {vector<int>in(numCourses,0);unordered_map<int,vector<int>>end;for(auto&tmp:prerequisites){int a=tmp[0],b=tmp[1];end[b].push_back(a);in[a]++;}queue<int>q;vector<int>ret;for(int i=0;i<numCourses;i++){if(in[i]==0){q.push(i);}}while(q.size()){int a=q.front();q.pop();ret.push_back(a);for(auto&tmp:end[a]){in[tmp]--;if(in[tmp]==0){q.push(tmp);}}}if(ret.size()==numCourses) return ret;else return {};}
};