devbox
2023面试高手
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

算法训练营 - 广度优先BFS_图的bfs模板

作者：2023面试高手 | 2024-06-05 15:59:16

赞

踩

图的bfs模板

 

目录

从层序遍历开始

 N 叉树的层序遍历

经典BFS最短路模板

经典C++ queue

 数组模拟队列

 打印路径

示例1.bfs查找所有连接方块

C++queue版

 数组模拟队列

示例2.从多个位置同时开始BFS

示例3.抽象最短路类（作图关键）

示例4.跨过障碍的最短路

从层序遍历开始

        广度优先搜索（Breadth First Search，BFS），又称为宽度优先搜索，是最常见的图搜索方法之一。广度优先搜索是从某个顶点（源点）出发，一次性访问所有未被访问的邻接点，再依次从这些访问过邻接点出发，…，似水中涟漪，似声音传播，一层层地传播开来。
广度优先遍历是按照广度优先搜索的方式对图进行遍历。
 

广度优先搜索模型

Bfs()

{

        1. 建立起始步骤，队列初始化

        2. 遍历队列中的每一种可能，whlie(队列不为空)

        {

                通过队头元素带出下一步的所有可能，并且依次入队

                {

                        判断当前情况是否达成目标：按照目标要求处理逻辑

                }

                继续遍历队列中的剩余情况

        }

}

（看不懂没有关系，直接看题就完事儿了）

 N 叉树的层序遍历

力扣

  1. /*
  2. // Definition for a Node.
  3. class Node {
  4. public:
  5.     int val;
  6.     vector<Node*> children;
  8.     Node() {}
  10.     Node(int _val) {
  11.         val = _val;
  12.     }
  14.     Node(int _val, vector<Node*> _children) {
  15.         val = _val;
  16.         children = _children;
  17.     }
  18. };
  19. */
  20.  
  21. class Solution {
  22. public:
  23.     vector<vector<int>> levelOrder(Node* root) {
  24.         vector<int> v;
  25.         vector<vector<int>> vec;
  26.         queue<Node*> q;
  27.         if(!root) return vec;
  28.         q.push(root);//将开始bfs位置入队
  29.         while(!q.empty())
  30.         {
  31.             int n=q.size();//需要遍历这一层的元素个数
  32.             for(int i=0;i<n;i++)//记录该层元素并将其所连接的点入队
  33.             {
  34.                 Node* temp=q.front();
  35.                 q.pop();
  36.                 if(!temp) continue;
  37.                 v.push_back(temp->val);
  38.                 //将这个点所连接的点入队
  39.                 vector<Node*> son=temp->children;
  40.                 for(int j=0;j<son.size();j++)
  41.                     q.push(son[j]);                
  42.             }
  43.             vec.push_back(v);
  44.             v.clear();
  45.         }
  46.         return vec;
  47.     }
  48. };

经典BFS最短路模板

经典C++ queue

  1. #include <iostream>
  2. #include <cstring>
  3. #include <queue>
  4. using namespace std;
  5.  
  6. const int N = 110;
  7. typedef pair<int, int> PII;
  8. int n, m;
  9. int g[N][N], d[N][N];
  10.  
  11. int bfs()
  12. {
  13.     queue< pair<int, int> > q;
  14.     q.push({0, 0});
  15.     memset(d, -1, sizeof(d));
  16.     d[0][0] = 0;
  17.  
  18.     int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
  19.  
  20.     while (q.size())//队列不为空
  21.     {
  22.         PII t = q.front();//取队头元素
  23.         q.pop();//出队
  24.         for (int i = 0; i < 4; i++)
  25.         {
  26.             int x = t.first + dx[i], y = t.second + dy[i];
  27.  
  28.             if (x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1)
  29.             {
  30.                 d[x][y] = d[t.first][t.second] + 1;//当前点到起点的距离
  31.                 q.push({x, y});//将新坐标入队
  32.             }
  33.         }
  34.     }
  35.     return d[n - 1][m -1];
  36. }
  37.  
  38. int main()
  39. {
  40.     cin >> n >> m;
  41.     for (int i = 0; i < n; i++)
  42.         for (int j = 0; j < m; j++)
  43.             cin >> g[i][j];
  44.  
  45.     cout << bfs() << endl;
  46.  
  47.     return 0;
  48. }
  49.

 数组模拟队列

  1. #include<iostream>
  2. #include<cstring>
  3. #include<algorithm>
  4. using namespace std;
  5. const int N = 110; 
  6. typedef pair<int, int> PII;
  7. int n, m;
  8. int g[N][N];//存放地图
  9. int d[N][N];//存 每一个点到起点的距离
  10. PII q[N * N];//手写队列
  11. int bfs()
  12. {
  13.     int hh = 0, tt = 0;
  14.     q[0] = {0, 0};
  15.     memset(d, - 1, sizeof d);//距离初始化为- 1表示没有走过
  16.     d[0][0] = 0;//表示起点走过了
  17.  
  18.     int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};//x 方向的向量和 y 方向的向量组成的上、右、下、左
  19.  
  20.     while(hh <= tt)//队列不空
  21.     {
  22.         PII t = q[hh ++ ];//取队头元素
  23.  
  24.         for(int i = 0; i < 4; i ++ )//枚举4个方向
  25.         {
  26.             int x = t.first + dx[i], y = t.second + dy[i];//x表示沿着此方向走会走到哪个点
  27.             if(x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1)//在边界内 并且是空地可以走 且之前没有走过
  28.             {
  29.                 d[x][y] = d[t.first][t.second] + 1;//到起点的距离
  30.                 q[ ++ tt ] = {x, y};//新坐标入队
  31.             }
  32.         }
  33.     }
  34.     return d[n - 1][m - 1]; //输出右下角点距起点的距离即可
  35. }
  36. int main() 
  37. {
  38.     cin >> n >> m;
  39.     for(int i = 0; i < n; i ++ )
  40.         for(int j = 0; j < m; j ++ )
  41.             cin >> g[i][j];
  42.  
  43.     cout << bfs() << endl;
  44.  
  45.     return 0;
  46. }
  47.  
  48.

 打印路径

  1. #include<iostream>
  2. #include<cstring>
  3. #include<algorithm>
  4. using namespace std;
  5. const int N = 110;
  6. typedef pair<int, int> PII;
  7. PII q[N*N],Prev[N][N];
  8. int g[N][N], d[N][N];
  9. int n, m;
  10. int bfs()
  11. {
  12.     int hh = 0, tt = 0;
  13.     q[0] = {0, 0};
  14.     memset(d, -1, sizeof d);
  15.  
  16.     int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
  17.     d[0][0] = 0;
  18.     while(hh <= tt)
  19.     {
  20.         PII t = q[hh ++ ];
  21.         for(int i = 0; i < 4; i ++ )
  22.         {
  23.             int x = dx[i] + t.first, y = t.second + dy[i];
  24.  
  25.             if(x >= 0 && x < n && y >= 0 && y < m && g[x][y] == 0 && d[x][y] == -1)
  26.             {
  27.                 d[x][y] = d[t.first][t.second] + 1;
  28.                 Prev[x][y] = t;
  29.                 q[++ tt] = {x, y};
  30.             }
  31.         }
  32.     }
  33.     int x = n - 1, y = m - 1;
  34.     while(x || y)//有一个不d等于0
  35.     {
  36.         cout << x << ' ' << y << endl;
  37.         PII t = Prev[x][y];
  38.         x = t.first, y = t.second;
  39.     }
  40.  
  41.     return d[n - 1][m - 1];
  42. }
  43. int main()
  44. {
  45.     cin >> n >> m;
  46.     for(int i = 0; i < n; i ++ )
  47.         for(int j = 0; j < m;j ++)
  48.             cin >> g[i][j];
  49.  
  50.     cout << bfs() << endl;
  51.  
  52.     return 0;
  53. }
  54.

输入

  1. 5 5
  2. 0 1 0 0 0
  3. 0 1 0 1 0
  4. 0 0 0 0 0
  5. 0 1 1 1 0
  6. 0 0 0 1 0

输出

  1. 4 4
  2. 3 4
  3. 2 4
  4. 2 3
  5. 2 2
  6. 2 1
  7. 2 0
  8. 1 0
  9. 8

示例1.bfs查找所有连接方块

力扣

 思路：

非常简单，就是把图块的四个方向都搜索一遍，对于每个相邻的同色图块修改成新色即可

C++queue版

  1. class Solution {
  2. public:
  3.     const int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
  4.     vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
  5.         int old=image[sr][sc];
  6.         if(old==color) return  image;
  7.  
  8.         int n=image.size(),m=image[0].size();
  9.         queue<pair<int,int>> q;
  10.         q.push({sr,sc});
  11.         image[sr][sc]=color;
  12.  
  13.         while(!q.empty())
  14.         {
  15.             pair<int,int> t=q.front();
  16.             q.pop();
  17.             for(int i=0;i<4;i++)
  18.             {
  19.                 int x=t.first+dx[i],y=t.second+dy[i];
  20.                 if(x>=0&&x<n&&y>=0&&y<m&&image[x][y]==old)
  21.                 {
  22.                     q.push({x,y});
  23.                     image[x][y]=color;
  24.                 }
  25.             }
  26.         }
  27.         return image;
  28.     }
  29. };

 数组模拟队列

  1. class Solution {
  2. public:
  3.     const int dx[4] = {1, 0, 0, -1},dy[4] = {0, 1, -1, 0};
  4.     vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
  5.         int old = image[sr][sc];
  6.         if (old == color) return image;
  7.         
  8.         int n = image.size(), m = image[0].size();
  9.         int hh=0,tt=0;
  10.         pair<int,int> q[n*m];
  11.         q[0]={sr,sc};
  12.         image[sr][sc] = color;
  13.         while (hh<=tt) {
  14.             pair<int,int> t=q[hh++];
  15.             for (int i = 0; i < 4; i++) {
  16.                 int x = t.first+dx[i], y = t.second+dy[i];
  17.                 if (x >= 0 && x < n && y >= 0 && y < m && image[x][y] == old) {
  18.                     q[++tt]={x,y};
  19.                     image[x][y] = color;
  20.                 }
  21.             }
  22.         }
  23.         return image;
  24.     }
  25. };
  26.

示例2.从多个位置同时开始BFS

力扣

本题可以先找到所有的腐烂橘子，入队，用第一批带出新一批腐烂的橘子

每以匹橘子都会在一分钟之内腐烂,所以此题可以转化为求BFS执行的大循环的次数

这里的step的更新需要有一个标记，只有新的腐烂的橘子加入，step才能自加

最后BFS执行完之后，说明所有可以被腐烂的都完成了，再去遍历grid,如何还有

值为1的，说明没有办法完全腐烂，返回-1,如果没有，则返回step

  1. class Solution {
  2. public:
  3.     int dx[4]={1,-1,0,0},dy[4]={0,0,1,-1};
  4.     int orangesRotting(vector<vector<int>>& grid) {
  5.         int n=grid.size(),m=grid[0].size();
  6.         queue<pair<int,int>> q;
  7.         int cnt=0;
  8.         int step=0;
  9.  
  10.         for(int i=0;i<n;i++)
  11.             for(int j=0;j<m;j++)
  12.                 if(grid[i][j]==2) q.push({i,j});
  13.                 else if(grid[i][j]==1) cnt++;
  14.  
  15.         while(!q.empty())
  16.         {
  17.             int tot=q.size();
  18.             bool flag=false;
  19.             while(tot--)//多个位置同时开始
  20.             {
  21.                 pair<int,int> t=q.front();
  22.                 q.pop();
  23.                 for(int i=0;i<4;i++)
  24.                 {
  25.                     int x=t.first+dx[i],y=t.second+dy[i];
  26.                     if(x>=0&&x<n&&y>=0&&y<m&&grid[x][y]==1)
  27.                     {
  28.                         q.push({x,y});
  29.                         grid[x][y]=2;
  30.                         cnt--;
  31.                         flag=true;
  32.                     }
  33.                 }
  34.             }
  35.             if(flag) ++step;
  36.             
  37.         }
  38.         return cnt?-1:step;   
  39.     }
  40. };

示例3.抽象最短路类（作图关键）

力扣

 思路：

  1. 通过BFS, 首先用beginWord带出转换一个字母之后所有可能的结果
  2. 每一步都要把队列中上一步添加的所有单词转换一遍，最短的转换肯定在这些单词当中， 所有这些词的转换只能算一次转换，因为都是上一步转换出来的，这里对于每个单词的每个位置都可以用26个字母进行转换，所以一个单词一次转换的可能有：单词的长度 * 26
  3. 把转换成功的新词入队，进行下一步的转换
  4. 最后整个转换的长度就和BFS执行的次数相同

 

  1. class Solution {
  2. public:
  3. 	int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
  4. 		//hash表的查询效率最高,将单词存入哈希表
  5. 		unordered_set<string> wordDict(wordList.begin(), wordList.end());
  6. 		//标记单词是否已经访问过，访问过的不再访问
  7. 		unordered_set<string> visited;
  8. 		visited.insert(beginWord);
  9. 		//初始化队列
  10. 		queue<string> q;
  11. 		q.push(beginWord);
  12. 		int res = 1;
  13. 		while (!q.empty()) 
  14.         {
  15. 			int nextSize = q.size();
  16.             while (nextSize--)
  17.             {
  18.                 string curWord = q.front();
  19.                 q.pop();
  20.                 if (curWord == endWord)
  21.                     return res ;
  22.                 //尝试转换当前单词的每一个位置
  23.                 for (int i = 0; i < curWord.size(); i++) 
  24.                 {
  25.                     string newWord = curWord;
  26.                     //每一个位置用26个字母分别替换
  27.                     for (char ch = 'a'; ch <= 'z'; ch++) 
  28.                     {
  29.                         newWord[i] = ch;
  30.                         //在字典里且没有用过
  31.                         if (wordDict.count(newWord) && !visited.count(newWord))
  32.                         {
  33.                             visited.insert(newWord);//标记用过
  34.                             q.push(newWord);
  35.                         }                       
  36.                     }
  37.                 }
  38.             }
  39. 			res++;
  40. 		}
  41. 		//转换不成功，返回0
  42. 		return 0;
  43. 	}
  44. };

示例4.跨过障碍的最短路

力扣

障碍指不可到达的路径，这种障碍一般用数组或者hash表存储，用if判断此路不通；

思路：

深度优先不适合解此题，递归深度太大，会导致栈溢出

本题的密码为4位密码，每位密码可以通过拨动一次进行改变，注意这里的数的回环以及拨动的方向

拨动方向：向前，向后

回环：如果当前是9，0时，向前，向后拨动需要变成最小最大，而不是简单的自加自减

  1. class Solution {
  2. public:
  3. 	int openLock(vector<string>& deadends, string target) {
  4. 		// 哈希表的查找更快
  5. 		unordered_set<string> deadendsSet(deadends.begin(), deadends.end());
  6. 		//如果"0000"在死亡字符串中，则永远到达不了
  7. 		if (deadendsSet.find("0000") != deadendsSet.end())
  8. 			return -1;
  9. 		//初始化队列
  10. 		queue<string> que;
  11. 		que.push("0000");
  12. 			//加标记，已经搜索过的字符串不需要再次搜索
  13. 			unordered_set<string> book;
  14. 		book.insert("0000");
  15. 		int step = 0;
  16. 		while (!que.empty()) {
  17. 			int n = que.size();
  18. 			//从上一步转换之后的字符串都需要进行验证和转换
  19. 			//并且只算做一次转换，类似于层序遍历，转换的步数和层相同
  20. 			//同一层的元素都是经过一步转换得到的
  21. 			while(n--) 
  22.             {
  23. 				string curStr = que.front();
  24. 				que.pop();
  25. 				if (curStr == target) return step;
  26. 				//四位密码锁，每个位置每次都可以转一次
  27. 				for (int j = 0; j < 4; j++) 
  28.                 {
  29. 					string newStr1 = curStr, newStr2 = curStr;
  30. 					//当前位置可以向前或者向后拨一位
  31. 					newStr1[j] = newStr1[j] == '9' ? '0' : newStr1[j] + 1;
  32. 					newStr2[j] = newStr2[j] == '0' ? '9' : newStr2[j] - 1;
  33.                     //如果不会死锁且没有尝试过，则入队
  34. 					if (deadendsSet.find(newStr1) == deadendsSet.end()
  35. 						&& book.find(newStr1) == book.end()) {
  36. 						que.push(newStr1);
  37. 						book.insert(newStr1);
  38. 					}
  39. 					if (deadendsSet.find(newStr2) == deadendsSet.end()
  40. 						&& book.find(newStr2) == book.end()) {
  41. 						que.push(newStr2);
  42. 						book.insert(newStr2);
  43. 					}
  44. 				}
  45. 			}
  46. 			step++;
  47. 		}
  48. 		return -1;
  49. 	}
  50. };

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/2023面试高手/article/detail/677159
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号