南京网站推广,移动端网页界面设计,淘数据官网,手机餐饮网站开发BFS#xff0c;全名为广度优先搜索(Breadth-First Search)#xff0c;是一种用于图或树的遍历或搜索的算法。它的主要思想是由节点自身开始向它的邻居节点新进展开搜索#xff0c;因此也常被形象地称为“层序遍历”。
BFS 基本思想
BFS 工作原理是#xff0c;从开始节点开…
BFS全名为广度优先搜索(Breadth-First Search)是一种用于图或树的遍历或搜索的算法。它的主要思想是由节点自身开始向它的邻居节点新进展开搜索因此也常被形象地称为“层序遍历”。
BFS 基本思想
BFS 工作原理是从开始节点开始在访问节点的邻居节点之前我们先访问其它节点。换句话说我们旧基于当前层次来遍历节点然后移至下一层再遍历节点。BFS 是以一种队列Queue结构的方式运行的首先我们有一个包含开始节点的队列然后
- 我们从队列的前端取出一个节点
- 为了防止回溯和重复访问我们会标记取出的节点为已访问
- 针对取出的节点把尚未访问过的邻居节点全部加入队列
- 我们重复以上步骤直至队列为空通过以上步骤你将会发现你在访问节点的时候首先访问的是距离开始节点最近的节点层次最低的节点然后层次逐渐提升这就是 BFS 的特性。
BFS 伪代码模板
BFS 主要应用于树和图结构的遍历因此伪代码也大致分为对应的两类以下都是基于未标记图进行的操作
树的广度优先搜索
function BFS(root) {initialize queue;queue.push(root);while(!queue.empty()) {node queue.front();queue.pop();process(node); //处理节点nodes generate_related_nodes(node); //获取与节点相关的未访问过的子节点queue.push(nodes);}
}图的广度优先搜索
function BFS(graph, start) {initialize queue and visited set;queue.push(start);visited.insert(start);while(!queue.empty()) {node queue.front();queue.pop();process(node); //处理节点nodes generate_related_nodes(node); //获取与节点相关的邻居节点for(node in nodes) {if(node not in visited) { //如果邻居节点尚未访问过queue.push(node);visited.add(node);}}}
}接下来举出六个BFS经典问题详细介绍和解题思路
二叉树的层次遍历
在这个问题中我们需要通过 BFS 遍历二叉树的每一层以二维数组的形式返回结果。
vectorvectorint levelOrder(TreeNode* root) {if (!root) return {};vectorvectorint result;queueTreeNode* q;q.push(root);while (!q.empty()) {vectorint one_level;for (int i q.size(); i 0; i--) {TreeNode* node q.front();q.pop();one_level.push_back(node-val);if (node-left) q.push(node-left);if (node-right) q.push(node-right);}result.push_back(one_level);}return result;
}岛屿的个数
给定一个由 ‘1’陆地和 ‘0’水组成的的二维网格计算岛屿的数量。
解题思路主要是遍历二维数组当遇到 ‘1’ 时通过 BFS 搜索并 ‘感染’ 周围的 ‘1’最后计算 ‘1’ 的个数。
int dx[4] {-1, 1, 0, 0};
int dy[4] {0, 0, -1, 1};void bfs(vectorvectorchar grid, int x, int y, int row, int col) {queuepairint, int q;q.push({x, y});grid[x][y] 0; // 把 1 感染为 0while (!q.empty()) {auto [r, c] q.front();q.pop();for (int i 0; i 4; i) {int nx r dx[i], ny c dy[i];if (nx 0 nx row ny 0 ny col grid[nx][ny] 1) {q.push({nx, ny});grid[nx][ny] 0;}}}
}int numIslands(vectorvectorchar grid) {int row grid.size();if (row 0) {return 0;}int col grid[0].size();int res 0;for (int i 0; i row; i) {for (int j 0; j col; j) {if (grid[i][j] 1) {bfs(grid, i, j, row, col);res; // 计算岛屿数量}}}return res;
}打开密码锁的最少步数
给你一个初始为 ‘0000’ 的四位密码你可以每次对密码的任意一位做上下旋转旋转一次可以将该位的数字增加 1 或减少 1 。求出最少的旋转次数使得密码等于 target 。
int openLock(vectorstring deadends, string target) {unordered_setstring dead(deadends.begin(), deadends.end());if (dead.count(0000)) return -1;if (target 0000) return 0;unordered_mapstring, int dist{{0000, 0}};queuestring q;q.push(0000);while (!q.empty()) {string t q.front(); q.pop();for (int i 0; i 4; i) {for (int j -1; j 1; j 2) {string str t;str[i] (str[i] - 0 j 10) % 10 0;if (str target) return dist[t] 1;if (!dead.count(str) !dist.count(str)) {dist[str] dist[t] 1;q.push(str);}}}}return -1;
}图中两点间最短路径长度
给定一个无向图求从起点 s 到终点 t最短路径长度是多少。
vectorunordered_setint g; // 图
unordered_mapint, int dist; // 从起点到每个点的距离int bfs(int s, int t) {queueint q;q.push(s);dist[s] 0;while (!q.empty()) {int x q.front(); q.pop();for (int y : g[x]) {if (!dist.count(y)) {dist[y] dist[x] 1;q.push(y);}}}return dist[t];
}找到最近的医院
给定一个二维的 0-1 矩阵1 表示医院0 表示型房屋。求每个房屋距离最近医院的距离。
vectorvectorint dirs {{-1,0}, {1,0}, {0,-1}, {0,1}};vectorvectorint findNearestHospital(vectorvectorint grid) {int m grid.size(), n grid[0].size();vectorvectorint dist(m, vectorint(n, INT_MAX));queuepairint, int q;// BFS 队列// 先把所有的医院节点放进队列然后开始 BFSfor(int i 0; i m; i) {for(int j 0; j n; j) {if(grid[i][j] 1) {dist[i][j] 0;q.push({i, j});}}}while(!q.empty()) {auto cur q.front(); q.pop();for(auto dir : dirs) {int nx cur.first dir[0], ny cur.second dir[1];if(nx 0 ny 0 nx m ny n) {if(dist[nx][ny] dist[cur.first][cur.second] 1) {dist[nx][ny] dist[cur.first][cur.second] 1;q.push({nx, ny});}}}}return dist;
}最小基因变异
给定两个基因序列 start 和 end一个基因库表 bank求出把 start 变到 end 所需要的最小变异次数。一次基因变化代表改变一个字母。
int minMutation(string start, string end, vectorstring bank) {unordered_setstring dict(bank.begin(), bank.end());if (!dict.count(end)) return -1;unordered_mapstring, int dist{{start, 0}};queuestring q;q.push(start);while (!q.empty()) {string gene q.front(); q.pop();if (gene end) return dist[gene];for (int i 0; i gene.size(); i) {string newGene gene;for (char c : ACGT) {newGene[i] c;if (dict.count(newGene) !dist.count(newGene)) {dist[newGene] dist[gene] 1;q.push(newGene);}}}}return -1;
}如果你想更深入地了解人工智能的其他方面比如机器学习、深度学习、自然语言处理等等也可以点击这个链接我按照如下图所示的学习路线为大家整理了100多G的学习资源基本涵盖了人工智能学习的所有内容包括了目前人工智能领域最新顶会论文合集和丰富详细的项目实战资料可以帮助你入门和进阶。
链接 人工智能交流群【最新顶会与项目实战】点击跳转
