目录宽度优先搜索的核心思想算法实现步骤BFS的特点和应用场景BFS 在树结构的应用BFS 在 FloodFill 算法的应用边权为 1 的最短路径问题1、单源最短路问题2、多源最短路问题BFS 解决拓扑排序宽度优先搜索的核心思想想象一下你在玩一个迷宫游戏你站在起点想知道最快到达终点的路线。BFS的策略是首先探索所有起点直接相连的位置第一层。然后探索所有与第一层位置直接相连的、且未被访问过的位置第二层。接着探索所有与第二层位置直接相连的、且未被访问过的位置第三层。... 以此类推直到找到终点或者遍历完所有能到达的点。这种“由近及远”的搜索方式保证了一旦找到目标所用的步数或路径长度一定是最短的。算法实现步骤BFS通常使用一个队列Queue 这种数据结构来辅助实现。队列的特点是“先进先出”FIFO这正好符合我们“先访问的节点其邻居也先被访问”的需求。步骤分解初始化选择一个起始节点将其标记为 “已访问”。将该起始节点放入队列。循环执行以下步骤直到队列为空a. 出队从队列的头部取出一个节点我们称它为“当前节点”。b. 处理访问当前节点例如检查它是否是目标节点或者进行其他操作。c. 将当前节点的所有“未访问”的邻居节点标记为“已访问”并依次放入队列的尾部结束当队列为空时说明所有从起点可达的节点都已经被访问过了算法结束。一个生动的例子0 / \ 1 2 / \ \ 3 4 5步骤模拟步骤队列状态 (队首- ... -队尾)当前节点访问顺序动作说明初始[0]--将起点0放入队列1[1, 2]00取出0访问它。将0的未访问邻居1, 2加入队列。2[2, 3, 4]11取出1访问它。将1的未访问邻居3, 4加入队列。3[3, 4, 5]22取出2访问它。将2的未访问邻居5加入队列。4[4, 5]33取出3访问它。3没有未访问的邻居。5[5]44取出4访问它。4没有未访问的邻居。6[]55取出5访问它。5没有未访问的最终的访问顺序BFS遍历序列是0, 1, 2, 3, 4, 5。你可以看到这正是一层一层输出的结果。BFS的特点和应用场景特点完备性如果解存在BFS一定能找到。最优性在无权图中BFS找到的路径一定是最短路径。空间复杂度高在最坏情况下需要存储一整层的节点应用场景图的连通性判断两个节点是否连通。最短路径在无权图中求两点间的最短路径。迷宫求解找到从起点到终点的最短路径。社交网络查找“度”关系例如寻找三度好友。序列变换如单词接龙问题。树的层序遍历。BFS 在树结构的应用层序遍历题目链接解析采用广度优先搜索但难点是不知道每层具体有多少结点也就不知道要把多少结果放在数组的同一行解决方法是在遍历队列之前用一个变量先记录一下队列的长度然后执行长度次访问队头的操作执行完后再次记录队列的长度下一次遍历队列时就访问长度次......以此类推。/* // Definition for a Node. class Node { public: int val; vectorNode* children; Node() {} Node(int _val) { val _val; } Node(int _val, vectorNode* _children) { val _val; children _children; } }; */ class Solution { public: vectorvectorint levelOrder(Node* root) { queueNode* q; vectorvectorint ret; if(root) q.push(root); int i 0; while(!q.empty()) { ret.resize(i 1); // 为下一次记录结果开辟空间 int sz q.size(); // 记录这一层的结点个数 while(sz--) { // 访问对头 ret[i].push_back((q.front())-val); // 把对头的子结点加入队列 for(auto j : (q.front())-children) { q.push(j); } // 对头已经访问完了出队列 q.pop(); } i; } return ret; } };题目链接解析先进行二叉树的层序遍历最后将结果数组的对应部分进行逆序class Solution { public: vectorvectorint zigzagLevelOrder(TreeNode* root) { vectorvectorint ret; queueTreeNode* q; int sz 0; int i 0; if(root) q.push(root); while(!q.empty()) { sz q.size(); ret.resize(i 1); while(sz--) { TreeNode* top q.front(); ret[i].push_back(top-val); q.pop(); if(top-left) q.push(top-left); if(top-right) q.push(top-right); } i; } for(int j 1; j ret.size(); j 2) { reverse(ret[j].begin(),ret[j].end()); } return ret; } };题目链接解析以从左到右从上到下从根结点开始为 1依次对非空结点进行编号可以发现如果根结点的编号为 n 那么它的左孩子和右孩子的编号分别为 2*n 和 2*n 1树某行的宽度 最右边的结点编号 - 最左边结点编号 1。对树进行层序遍历队列中每个元素存储结点和结点的编号。class Solution { public: int widthOfBinaryTree(TreeNode* root) { queuepairTreeNode*,unsigned int q; if(root) q.push(make_pair(root,1)); unsigned maxlen 0; while(!q.empty()) { pairTreeNode*,unsigned int front q.front(); pairTreeNode*,unsigned int back q.back(); if(back.second - front.second 1 maxlen) maxlen back.second - front.second 1; int sz q.size(); while(sz--) { pairTreeNode*,unsigned int front q.front(); if((front.first)-left) q.push(make_pair((front.first)-left,front.second * 2)); if((front.first)-right) q.push(make_pair((front.first)-right,front.second * 2 1)); q.pop(); } } return maxlen; } };BFS 在 FloodFill 算法的应用题目链接解析先判断源头是否是给定的color如果是直接返回。如果不是把源头加入队列并立刻染色然后开始循环每次取出对头元素然后看看它上下左右的像素是否有 oldcolor如果有加入队列并立刻染色。重复上述步骤直到队列为空。注意元素一进入队列就要立刻染色不要在取出对头元素时再染色。class Solution { typedef pairint,int PII; public: vectorvectorint floodFill(vectorvectorint image, int sr, int sc, int color) { if(image[sr][sc] color) return image; int oldcolor image[sr][sc]; int w image.size(); // 宽 int l image[0].size(); // 长 queuePII q; q.push({sr,sc}); image[sr][sc] color; vectorvectorint dp {{0,1},{1,0},{-1,0},{0,-1}}; while(!q.empty()) { auto [a,b] q.front(); q.pop(); for(int i 0; i 4; i) { int m a dp[i][0]; int n b dp[i][1]; if(m 0 m w n 0 n l image[m][n] oldcolor) { q.push({m,n}); image[m][n] color; } } } return image; } };题目链接解析遍历整个二维数组如果遇到 ‘1’ 判断它先前有没有被标记过如果没有就以这个 ‘1’ 为源点进行 FloodFill 算法同时岛屿数量 1。如何标记已访问过的 ‘1’ : 有两种方式1、如果源数组允许被修改直接把已访问过的 ‘1’ 标记为 ‘0’2、如果源数组不允许被修改创建一个 vis 数组并初始化为全 false将已访问过的位置标记为 true。class Solution { public: vectorvectorint dp {{0,1},{1,0},{-1,0},{0,-1}}; int w; int l; int numIslands(vectorvectorchar grid) { w grid.size(); l grid[0].size(); int num 0; for(int i 0; i w; i) { for(int j 0; j l; j) { if(grid[i][j] 1) { num; bfs(grid,i,j); } } } return num; } void bfs(vectorvectorchar grid,int i,int j) { queuepairint,int q; q.push({i,j}); grid[i][j] 0; while(q.size()) { auto [a,b] q.front(); q.pop(); for(int k 0; k 4; k) { int x a dp[k][0]; int y b dp[k][1]; if(x 0 x w y 0 y l grid[x][y] 1) { q.push({x,y}); grid[x][y] 0; } } } } };腐烂的苹果_牛客题霸_牛客网注意ret 必须初始化为 -1因为如果所有的苹果都是腐烂的最后的结果应该是 0。class Solution { public: /** * 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可 * * * param grid int整型vectorvector * return int整型 */ typedef pairint,int PII; int row; int col; int ret -1; vectorint dx {0,0,1,-1}; vectorint dy {1,-1,0,0}; void bfs(vectorvectorint grid) { queuePII q; for(int i 0; i row; i) { for(int j 0; j col; j) { if(grid[i][j] 2) { q.push({i,j}); } } } while(q.size()) { int sz q.size(); while(sz--) { PII t q.front(); q.pop(); for(int i 0; i 4; i) { int x t.first dx[i]; int y t.second dy[i]; if(x 0 x row y 0 y col grid[x][y] 1) { grid[x][y] 2; q.push({x,y}); } } } ret; } } int rotApple(vectorvectorint grid) { // write code here row grid.size(); col grid[0].size(); bfs(grid); for(int i 0; i row; i) { for(int j 0; j col; j) { if(grid[i][j] 1) { return -1; } } } return ret; } };边权为 1 的最短路径问题1. 为什么使用 BFS在边权都为 1 的图中BFS 具有层序遍历的特性先访问距离起点为 1 的节点再访问距离起点为 2 的节点依此类推...这就天然保证了第一次访问某个节点时走过的路径就是最短路径。2. 为什么这能保证最短路径数学归纳法证明基础起点距离为 0正确归纳假设所有距离为 k 的节点都已正确标记步骤距离为 k 1 的节点只能从距离为 k 的节点到达结论BFS按距离递增顺序访问节点首次访问即最短距离BFS 解决边权为1最短路径问题的精髓所在——利用队列的先进先出特性自然地按距离从小到大的顺序遍历所有节点。利用 dist 数组存储起点到任意终点的最短距离dist 数组初始化将起点初始化为 0意思是起点到起点的最短路径是 0其余的都初始化为 -1意思是该点还没有更新过最短距离如何填写 dist 数组用队列顺序遍历所有节点时假设由 (x,y) 点遍历到 (a,b) 点如果 dist[a][b] 还没有更新过(即 dist[a][b] -1)那么dist[a][b] dist[x][y] 1。利用 cnt 数组存储起点到任意终点有多少条最短路径dist 数组的其他作用dist 数组不仅可以存储起点到任意终点的最短距离还可以帮助找出起点到任意终点有多少条最短路径。如何得出初始化 cnt 数组把起点处初始化为 1代表从起点到起点有一条最短路径其余都初始化为 0。如何填写 cnt 数组假设由 (x,y) 点遍历到 (a,b) 点在更新 dist 数组时dist[a][b] 有两种情况dist[a][b] -1说明我们是第一次到达 (a,b) 点此时的路径是最短的我们让 dist[a][b] dist[x][y] 1并且让 cnt[a][b] cnt[x][y]并且把 (a,b) 加入到队列。dist[a][b] ! -1说明我们不是第一次到达 (a,b) 点此时不更新 dist[a][b]。如果 dist[x][y] 1 dist[a][b] 那么我们又找到一条由起点到 (a,b) 点的最短路径此时让 cnt[a][b] cnt[x][y]。此时不把 (a,b) 加入到队列。1、单源最短路问题即只有一个起点和终点的问题题目链接解析从起点开始使用一次 BFS将起点加入队列只要队列不为空就进入循环每一轮都从队列弹出队列元素个数次的对头元素每轮弹出后使步数 1。每次弹出将对头元素的上下左右的 1、没有越界的 2、没有访问过的 3、不是墙的位置加入队列并立刻将它们标记为已访问检查它是否是一个出口如果是就返回步数否则继续循环。如果退出了循环说明没有出口。注意如果是在 main 函数内部实现采用 cout 输出答案的方式用 flag 标记是否找到终点如果找到终点要跳出两个循环class Solution { public: int nearestExit(vectorvectorchar m, vectorint e) { queuepairint,int q; vectorvectorbool vis(m.size(), vectorbool(m[0].size(),false)); vectorvectorint dp {{0,1},{1,0},{-1,0},{0,-1}}; int count 0; int row m[0].size(); int col m.size(); q.push({e[0],e[1]}); vis[e[0]][e[1]] true; pairint,int en({e[0],e[1]}); while(q.size()) { int n q.size(); while(n--) { auto [a,b] q.front(); q.pop(); pairint,int cur({a,b}); if(cur ! en (a 0 || a col - 1 || b 0 || b row - 1)) return count; for(int i 0; i 4; i) { int x a dp[i][0]; int y b dp[i][1]; if(x 0 x col y 0 y row !vis[x][y] m[x][y] .) { q.push({x,y}); vis[x][y] true; } } } count; } return -1; } };题目链接解析先检查最终的基因序列是否在bank如果不在返回 -1如果在记住它的下标。将起始序列加入一个队列只要队列有元素就开始循环先使步数1每一轮都从队列弹出队列元素个数次的对头元素每次弹出都将对头元素与 bank 的每个元素对比如果差异 1对头元素仅一次变化就可以变成 bank 中的某个元素就将 bank 的该元素加入队列并且标记该元素为已访问。如果退出循环表示不能合法的变化为最终序列返回 -1class Solution { public: int minMutation(string startGene, string endGene, vectorstring bank) { int aim -1; const int n bank.size(); int ret 0; vectorbool vis(n,false); for(int i 0; i n; i) { if(endGene bank[i]) { aim i; break; } } if(aim -1) return -1; queuestring q; q.push(startGene); while(q.size()) { int m q.size(); ret; while(m--) { string cur q.front(); q.pop(); for(int i 0; i n; i) { int d def(cur,bank[i]); if(d 1 !vis[i]) { if(i aim) return ret; q.push(bank[i]); vis[i] true; } } } } return -1; } int def(string a,string b) { int d 0; for(int i 0; i 8; i) { if(a[i] ! b[i]) d; } return d; } };2、多源最短路问题即有多个起点和一个终点的问题解法把多个起点看成是一个起点超级源点问题转换为单源最短路问题。有时候可以把终点看成起点正难则反代码如何写很简单把所有起点加入到队列所有起点标记为已访问之后的过程与单源最短路问题相同。BFS 解决拓扑排序知识铺垫1. 什么是“有向无环图”DAG我们可以通过拆解这个术语来理解它图 由顶点或称为节点和连接顶点的边组成的集合。有向 图中的边是有方向的。从顶点 A 到顶点 B 的边A → B与从 B 到 A 的边B → A是两条不同的边。这表示一种单向关系。无环 图中不存在任何循环。也就是说你无法从任何一个顶点出发沿着若干条有向边最终又回到该顶点本身。总结一下有向无环图就是一个带有方向边的图并且你不可能从某个节点开始沿着边的方向一直走最终又回到起点。2. 什么是AOV网AOV网是Activity On Vertex network的缩写中文意思是“用顶点表示活动的网络”或“活动在顶点上的网络”。它是一种特殊的有向图用于描述一个项目中各个活动任务之间的优先约束关系。顶点 代表活动或任务。例如一门课程、一个编译过程、一个生产步骤。有向边 代表活动之间的优先关系即依赖关系。如果存在一条从顶点 A 指向顶点 B 的有向边A, B则表示活动 A 必须在活动 B 开始之前完成。A 称为 B 的直接前驱B 称为 A 的直接后继。核心特性由于AOV网描述的是“先后次序”它绝对不能存在有向环。如果存在环比如 A→B→C→A就意味着 A 要在 B 之前完成B 要在 C 之前完成而 C 又要在 A 之前完成。这形成了一个逻辑悖论项目将永远无法开始。因此AOV网其实就是一个有向无环图。拓扑排序目标 将 DAG 中的所有顶点排成一个线性序列使得对图中任意一条有向边u, v在序列中u都出现在v的前面。通俗理解 就像是为一系列有先后顺序的任务比如上面的青椒炒肉工程图安排一个线性可执行的清单。这个清单必须保证所有前置任务都在后续任务之前完成。重要性质存在性 一个图能进行拓扑排序的充要条件是它是一个有向无环图。如果图中有环拓扑排序就无法进行。不唯一性 一个 DAG 的拓扑排序序列可能有多个。BFS 解决拓扑排序的算法实现算法步骤统计入度 遍历图计算每个顶点的入度有多少条边指向它。初始化队列 将所有入度为 0的顶点加入一个队列或栈、列表。当队列不为空时循环处理a. 从队列中取出一个顶点u并将其输出或存入结果列表。b. 遍历u的所有邻接顶点v将v的入度减 1相当于从图中移除边u, v。如果v的入度因此变为 0则将v加入队列。当队列为空时检查结果如果结果列表中的顶点数量等于图中的总顶点数则排序成功该列表即为拓扑排序之一。如果结果列表中的顶点数量小于总顶点数说明图中存在环无法进行拓扑排序。拓扑排序的应用之一判断有向图是否存在环如何建图使用邻接表建图即把某个结点作为邻接表的首元素把该结点指向的所有结点作为之后的元素题目链接class Solution { public: bool canFinish(int numCourses, vectorvectorint prerequisites) { vectorint in(numCourses,0); // 存储结点的入度 unordered_mapint,vectorint edges; // 邻接表建图 // 建立邻接表、记录结点的入度 for(auto e : prerequisites) { int a e[0]; int b e[1]; // b-a edges[b].push_back(a); in[a]; } // 把入度为 0 的结点加入队列 queueint q; for(int i 0; i numCourses; i) { if(in[i] 0) q.push(i); } // 拓扑排序 while(q.size()) { // 取出对头元素 int course q.front(); q.pop(); // 把对头元素指向的结点的入度减 1 // 同时把新产生的入度为 0 的结点加入队列 for(auto e : edges[course]) { in[e]--; if(in[e] 0) q.push(e); } } // 如果仍有入度不为 0 的结点说明存在环 for(int i 0; i numCourses; i) { if(in[i]) return false; } return true; } };
【算法】宽度优先遍历（BFS）
目录宽度优先搜索的核心思想算法实现步骤BFS的特点和应用场景BFS 在树结构的应用BFS 在 FloodFill 算法的应用边权为 1 的最短路径问题1、单源最短路问题2、多源最短路问题BFS 解决拓扑排序宽度优先搜索的核心思想想象一下你在玩一个迷宫游戏你站在起点想知道最快到达终点的路线。BFS的策略是首先探索所有起点直接相连的位置第一层。然后探索所有与第一层位置直接相连的、且未被访问过的位置第二层。接着探索所有与第二层位置直接相连的、且未被访问过的位置第三层。... 以此类推直到找到终点或者遍历完所有能到达的点。这种“由近及远”的搜索方式保证了一旦找到目标所用的步数或路径长度一定是最短的。算法实现步骤BFS通常使用一个队列Queue 这种数据结构来辅助实现。队列的特点是“先进先出”FIFO这正好符合我们“先访问的节点其邻居也先被访问”的需求。步骤分解初始化选择一个起始节点将其标记为 “已访问”。将该起始节点放入队列。循环执行以下步骤直到队列为空a. 出队从队列的头部取出一个节点我们称它为“当前节点”。b. 处理访问当前节点例如检查它是否是目标节点或者进行其他操作。c. 将当前节点的所有“未访问”的邻居节点标记为“已访问”并依次放入队列的尾部结束当队列为空时说明所有从起点可达的节点都已经被访问过了算法结束。一个生动的例子0 / \ 1 2 / \ \ 3 4 5步骤模拟步骤队列状态 (队首- ... -队尾)当前节点访问顺序动作说明初始[0]--将起点0放入队列1[1, 2]00取出0访问它。将0的未访问邻居1, 2加入队列。2[2, 3, 4]11取出1访问它。将1的未访问邻居3, 4加入队列。3[3, 4, 5]22取出2访问它。将2的未访问邻居5加入队列。4[4, 5]33取出3访问它。3没有未访问的邻居。5[5]44取出4访问它。4没有未访问的邻居。6[]55取出5访问它。5没有未访问的最终的访问顺序BFS遍历序列是0, 1, 2, 3, 4, 5。你可以看到这正是一层一层输出的结果。BFS的特点和应用场景特点完备性如果解存在BFS一定能找到。最优性在无权图中BFS找到的路径一定是最短路径。空间复杂度高在最坏情况下需要存储一整层的节点应用场景图的连通性判断两个节点是否连通。最短路径在无权图中求两点间的最短路径。迷宫求解找到从起点到终点的最短路径。社交网络查找“度”关系例如寻找三度好友。序列变换如单词接龙问题。树的层序遍历。BFS 在树结构的应用层序遍历题目链接解析采用广度优先搜索但难点是不知道每层具体有多少结点也就不知道要把多少结果放在数组的同一行解决方法是在遍历队列之前用一个变量先记录一下队列的长度然后执行长度次访问队头的操作执行完后再次记录队列的长度下一次遍历队列时就访问长度次......以此类推。/* // Definition for a Node. class Node { public: int val; vectorNode* children; Node() {} Node(int _val) { val _val; } Node(int _val, vectorNode* _children) { val _val; children _children; } }; */ class Solution { public: vectorvectorint levelOrder(Node* root) { queueNode* q; vectorvectorint ret; if(root) q.push(root); int i 0; while(!q.empty()) { ret.resize(i 1); // 为下一次记录结果开辟空间 int sz q.size(); // 记录这一层的结点个数 while(sz--) { // 访问对头 ret[i].push_back((q.front())-val); // 把对头的子结点加入队列 for(auto j : (q.front())-children) { q.push(j); } // 对头已经访问完了出队列 q.pop(); } i; } return ret; } };题目链接解析先进行二叉树的层序遍历最后将结果数组的对应部分进行逆序class Solution { public: vectorvectorint zigzagLevelOrder(TreeNode* root) { vectorvectorint ret; queueTreeNode* q; int sz 0; int i 0; if(root) q.push(root); while(!q.empty()) { sz q.size(); ret.resize(i 1); while(sz--) { TreeNode* top q.front(); ret[i].push_back(top-val); q.pop(); if(top-left) q.push(top-left); if(top-right) q.push(top-right); } i; } for(int j 1; j ret.size(); j 2) { reverse(ret[j].begin(),ret[j].end()); } return ret; } };题目链接解析以从左到右从上到下从根结点开始为 1依次对非空结点进行编号可以发现如果根结点的编号为 n 那么它的左孩子和右孩子的编号分别为 2*n 和 2*n 1树某行的宽度 最右边的结点编号 - 最左边结点编号 1。对树进行层序遍历队列中每个元素存储结点和结点的编号。class Solution { public: int widthOfBinaryTree(TreeNode* root) { queuepairTreeNode*,unsigned int q; if(root) q.push(make_pair(root,1)); unsigned maxlen 0; while(!q.empty()) { pairTreeNode*,unsigned int front q.front(); pairTreeNode*,unsigned int back q.back(); if(back.second - front.second 1 maxlen) maxlen back.second - front.second 1; int sz q.size(); while(sz--) { pairTreeNode*,unsigned int front q.front(); if((front.first)-left) q.push(make_pair((front.first)-left,front.second * 2)); if((front.first)-right) q.push(make_pair((front.first)-right,front.second * 2 1)); q.pop(); } } return maxlen; } };BFS 在 FloodFill 算法的应用题目链接解析先判断源头是否是给定的color如果是直接返回。如果不是把源头加入队列并立刻染色然后开始循环每次取出对头元素然后看看它上下左右的像素是否有 oldcolor如果有加入队列并立刻染色。重复上述步骤直到队列为空。注意元素一进入队列就要立刻染色不要在取出对头元素时再染色。class Solution { typedef pairint,int PII; public: vectorvectorint floodFill(vectorvectorint image, int sr, int sc, int color) { if(image[sr][sc] color) return image; int oldcolor image[sr][sc]; int w image.size(); // 宽 int l image[0].size(); // 长 queuePII q; q.push({sr,sc}); image[sr][sc] color; vectorvectorint dp {{0,1},{1,0},{-1,0},{0,-1}}; while(!q.empty()) { auto [a,b] q.front(); q.pop(); for(int i 0; i 4; i) { int m a dp[i][0]; int n b dp[i][1]; if(m 0 m w n 0 n l image[m][n] oldcolor) { q.push({m,n}); image[m][n] color; } } } return image; } };题目链接解析遍历整个二维数组如果遇到 ‘1’ 判断它先前有没有被标记过如果没有就以这个 ‘1’ 为源点进行 FloodFill 算法同时岛屿数量 1。如何标记已访问过的 ‘1’ : 有两种方式1、如果源数组允许被修改直接把已访问过的 ‘1’ 标记为 ‘0’2、如果源数组不允许被修改创建一个 vis 数组并初始化为全 false将已访问过的位置标记为 true。class Solution { public: vectorvectorint dp {{0,1},{1,0},{-1,0},{0,-1}}; int w; int l; int numIslands(vectorvectorchar grid) { w grid.size(); l grid[0].size(); int num 0; for(int i 0; i w; i) { for(int j 0; j l; j) { if(grid[i][j] 1) { num; bfs(grid,i,j); } } } return num; } void bfs(vectorvectorchar grid,int i,int j) { queuepairint,int q; q.push({i,j}); grid[i][j] 0; while(q.size()) { auto [a,b] q.front(); q.pop(); for(int k 0; k 4; k) { int x a dp[k][0]; int y b dp[k][1]; if(x 0 x w y 0 y l grid[x][y] 1) { q.push({x,y}); grid[x][y] 0; } } } } };腐烂的苹果_牛客题霸_牛客网注意ret 必须初始化为 -1因为如果所有的苹果都是腐烂的最后的结果应该是 0。class Solution { public: /** * 代码中的类名、方法名、参数名已经指定请勿修改直接返回方法规定的值即可 * * * param grid int整型vectorvector * return int整型 */ typedef pairint,int PII; int row; int col; int ret -1; vectorint dx {0,0,1,-1}; vectorint dy {1,-1,0,0}; void bfs(vectorvectorint grid) { queuePII q; for(int i 0; i row; i) { for(int j 0; j col; j) { if(grid[i][j] 2) { q.push({i,j}); } } } while(q.size()) { int sz q.size(); while(sz--) { PII t q.front(); q.pop(); for(int i 0; i 4; i) { int x t.first dx[i]; int y t.second dy[i]; if(x 0 x row y 0 y col grid[x][y] 1) { grid[x][y] 2; q.push({x,y}); } } } ret; } } int rotApple(vectorvectorint grid) { // write code here row grid.size(); col grid[0].size(); bfs(grid); for(int i 0; i row; i) { for(int j 0; j col; j) { if(grid[i][j] 1) { return -1; } } } return ret; } };边权为 1 的最短路径问题1. 为什么使用 BFS在边权都为 1 的图中BFS 具有层序遍历的特性先访问距离起点为 1 的节点再访问距离起点为 2 的节点依此类推...这就天然保证了第一次访问某个节点时走过的路径就是最短路径。2. 为什么这能保证最短路径数学归纳法证明基础起点距离为 0正确归纳假设所有距离为 k 的节点都已正确标记步骤距离为 k 1 的节点只能从距离为 k 的节点到达结论BFS按距离递增顺序访问节点首次访问即最短距离BFS 解决边权为1最短路径问题的精髓所在——利用队列的先进先出特性自然地按距离从小到大的顺序遍历所有节点。利用 dist 数组存储起点到任意终点的最短距离dist 数组初始化将起点初始化为 0意思是起点到起点的最短路径是 0其余的都初始化为 -1意思是该点还没有更新过最短距离如何填写 dist 数组用队列顺序遍历所有节点时假设由 (x,y) 点遍历到 (a,b) 点如果 dist[a][b] 还没有更新过(即 dist[a][b] -1)那么dist[a][b] dist[x][y] 1。利用 cnt 数组存储起点到任意终点有多少条最短路径dist 数组的其他作用dist 数组不仅可以存储起点到任意终点的最短距离还可以帮助找出起点到任意终点有多少条最短路径。如何得出初始化 cnt 数组把起点处初始化为 1代表从起点到起点有一条最短路径其余都初始化为 0。如何填写 cnt 数组假设由 (x,y) 点遍历到 (a,b) 点在更新 dist 数组时dist[a][b] 有两种情况dist[a][b] -1说明我们是第一次到达 (a,b) 点此时的路径是最短的我们让 dist[a][b] dist[x][y] 1并且让 cnt[a][b] cnt[x][y]并且把 (a,b) 加入到队列。dist[a][b] ! -1说明我们不是第一次到达 (a,b) 点此时不更新 dist[a][b]。如果 dist[x][y] 1 dist[a][b] 那么我们又找到一条由起点到 (a,b) 点的最短路径此时让 cnt[a][b] cnt[x][y]。此时不把 (a,b) 加入到队列。1、单源最短路问题即只有一个起点和终点的问题题目链接解析从起点开始使用一次 BFS将起点加入队列只要队列不为空就进入循环每一轮都从队列弹出队列元素个数次的对头元素每轮弹出后使步数 1。每次弹出将对头元素的上下左右的 1、没有越界的 2、没有访问过的 3、不是墙的位置加入队列并立刻将它们标记为已访问检查它是否是一个出口如果是就返回步数否则继续循环。如果退出了循环说明没有出口。注意如果是在 main 函数内部实现采用 cout 输出答案的方式用 flag 标记是否找到终点如果找到终点要跳出两个循环class Solution { public: int nearestExit(vectorvectorchar m, vectorint e) { queuepairint,int q; vectorvectorbool vis(m.size(), vectorbool(m[0].size(),false)); vectorvectorint dp {{0,1},{1,0},{-1,0},{0,-1}}; int count 0; int row m[0].size(); int col m.size(); q.push({e[0],e[1]}); vis[e[0]][e[1]] true; pairint,int en({e[0],e[1]}); while(q.size()) { int n q.size(); while(n--) { auto [a,b] q.front(); q.pop(); pairint,int cur({a,b}); if(cur ! en (a 0 || a col - 1 || b 0 || b row - 1)) return count; for(int i 0; i 4; i) { int x a dp[i][0]; int y b dp[i][1]; if(x 0 x col y 0 y row !vis[x][y] m[x][y] .) { q.push({x,y}); vis[x][y] true; } } } count; } return -1; } };题目链接解析先检查最终的基因序列是否在bank如果不在返回 -1如果在记住它的下标。将起始序列加入一个队列只要队列有元素就开始循环先使步数1每一轮都从队列弹出队列元素个数次的对头元素每次弹出都将对头元素与 bank 的每个元素对比如果差异 1对头元素仅一次变化就可以变成 bank 中的某个元素就将 bank 的该元素加入队列并且标记该元素为已访问。如果退出循环表示不能合法的变化为最终序列返回 -1class Solution { public: int minMutation(string startGene, string endGene, vectorstring bank) { int aim -1; const int n bank.size(); int ret 0; vectorbool vis(n,false); for(int i 0; i n; i) { if(endGene bank[i]) { aim i; break; } } if(aim -1) return -1; queuestring q; q.push(startGene); while(q.size()) { int m q.size(); ret; while(m--) { string cur q.front(); q.pop(); for(int i 0; i n; i) { int d def(cur,bank[i]); if(d 1 !vis[i]) { if(i aim) return ret; q.push(bank[i]); vis[i] true; } } } } return -1; } int def(string a,string b) { int d 0; for(int i 0; i 8; i) { if(a[i] ! b[i]) d; } return d; } };2、多源最短路问题即有多个起点和一个终点的问题解法把多个起点看成是一个起点超级源点问题转换为单源最短路问题。有时候可以把终点看成起点正难则反代码如何写很简单把所有起点加入到队列所有起点标记为已访问之后的过程与单源最短路问题相同。BFS 解决拓扑排序知识铺垫1. 什么是“有向无环图”DAG我们可以通过拆解这个术语来理解它图 由顶点或称为节点和连接顶点的边组成的集合。有向 图中的边是有方向的。从顶点 A 到顶点 B 的边A → B与从 B 到 A 的边B → A是两条不同的边。这表示一种单向关系。无环 图中不存在任何循环。也就是说你无法从任何一个顶点出发沿着若干条有向边最终又回到该顶点本身。总结一下有向无环图就是一个带有方向边的图并且你不可能从某个节点开始沿着边的方向一直走最终又回到起点。2. 什么是AOV网AOV网是Activity On Vertex network的缩写中文意思是“用顶点表示活动的网络”或“活动在顶点上的网络”。它是一种特殊的有向图用于描述一个项目中各个活动任务之间的优先约束关系。顶点 代表活动或任务。例如一门课程、一个编译过程、一个生产步骤。有向边 代表活动之间的优先关系即依赖关系。如果存在一条从顶点 A 指向顶点 B 的有向边A, B则表示活动 A 必须在活动 B 开始之前完成。A 称为 B 的直接前驱B 称为 A 的直接后继。核心特性由于AOV网描述的是“先后次序”它绝对不能存在有向环。如果存在环比如 A→B→C→A就意味着 A 要在 B 之前完成B 要在 C 之前完成而 C 又要在 A 之前完成。这形成了一个逻辑悖论项目将永远无法开始。因此AOV网其实就是一个有向无环图。拓扑排序目标 将 DAG 中的所有顶点排成一个线性序列使得对图中任意一条有向边u, v在序列中u都出现在v的前面。通俗理解 就像是为一系列有先后顺序的任务比如上面的青椒炒肉工程图安排一个线性可执行的清单。这个清单必须保证所有前置任务都在后续任务之前完成。重要性质存在性 一个图能进行拓扑排序的充要条件是它是一个有向无环图。如果图中有环拓扑排序就无法进行。不唯一性 一个 DAG 的拓扑排序序列可能有多个。BFS 解决拓扑排序的算法实现算法步骤统计入度 遍历图计算每个顶点的入度有多少条边指向它。初始化队列 将所有入度为 0的顶点加入一个队列或栈、列表。当队列不为空时循环处理a. 从队列中取出一个顶点u并将其输出或存入结果列表。b. 遍历u的所有邻接顶点v将v的入度减 1相当于从图中移除边u, v。如果v的入度因此变为 0则将v加入队列。当队列为空时检查结果如果结果列表中的顶点数量等于图中的总顶点数则排序成功该列表即为拓扑排序之一。如果结果列表中的顶点数量小于总顶点数说明图中存在环无法进行拓扑排序。拓扑排序的应用之一判断有向图是否存在环如何建图使用邻接表建图即把某个结点作为邻接表的首元素把该结点指向的所有结点作为之后的元素题目链接class Solution { public: bool canFinish(int numCourses, vectorvectorint prerequisites) { vectorint in(numCourses,0); // 存储结点的入度 unordered_mapint,vectorint edges; // 邻接表建图 // 建立邻接表、记录结点的入度 for(auto e : prerequisites) { int a e[0]; int b e[1]; // b-a edges[b].push_back(a); in[a]; } // 把入度为 0 的结点加入队列 queueint q; for(int i 0; i numCourses; i) { if(in[i] 0) q.push(i); } // 拓扑排序 while(q.size()) { // 取出对头元素 int course q.front(); q.pop(); // 把对头元素指向的结点的入度减 1 // 同时把新产生的入度为 0 的结点加入队列 for(auto e : edges[course]) { in[e]--; if(in[e] 0) q.push(e); } } // 如果仍有入度不为 0 的结点说明存在环 for(int i 0; i numCourses; i) { if(in[i]) return false; } return true; } };
