个人网站开发背景及意义,华军软件园下载中心,wordpress缩略图题目文本链接,做公司网站大概需要多少钱啊前言
在这篇文章之前#xff0c;已对非线性结构遍历的另一种方法——深度优先遍历进行了讲解#xff0c;其中很多概念词都是共用的。为了更好的阅读体验#xff0c;最好先在掌握或起码了解dfs的基础上#xff0c;再来阅读本文章#xff0c;否则因为会有很多概念词看不明白… 前言
在这篇文章之前已对非线性结构遍历的另一种方法——深度优先遍历进行了讲解其中很多概念词都是共用的。为了更好的阅读体验最好先在掌握或起码了解dfs的基础上再来阅读本文章否则因为会有很多概念词看不明白而降低阅读体验。
一命通关深度优先遍历-CSDN博客https://blog.csdn.net/qq_74260823/article/details/136819359?spm1001.2014.3001.5501 广度优先遍历
简介
与dfs不同bfs是先遍历完一层的所有结点再往下一层进发。bfs先踏完第一步能到达的所有结点然后再遍历第二步才可以到达的结点一直遍历到最远才可以到达的结点完成遍历。
但是同一个结点可能会在两个范围中 也可能会有回头路 不过所有的结点只能被遍历一次所以大部分bfs问题都需要配有一个标记数组。
实现方法
我们想知道第二步才可以到达的结点最直接的想法就是在找到所有第一步就能到达的情况下再走一步就是第二步才可以到达的结点。为了实现这个思想即通过上一层去找下一层的结点最直接的实现方法就是采用两个数组 我们遍历上层数组的所有元素然后通过这些元素找到他们相邻的结点就是下一层元素的所有元素。 然后继续往下遍历将上层数组清空与下层数组交换如此反复交替一直到走到最后一层。 不过这种方法可以优化成一个队列实现 将上一层的元素弹出的同时将下一层的元素带入队列尾这种方法思想在二叉树的层序遍历中已经详细讲过了就不再重复说明了。
因为解题思路和公式非常非常套路化所以直接上题目
200. 岛屿数量 - 力扣LeetCode 简单翻译一下题目就是找到有几个不挨着的1区块。 而解法也很简单我们遍历所有元素当遇到1时就采用bfs或者dfs将相邻的1全部标记一下我们这里用bfs来实现。
首先还是在dfs里一模一样的
位移数组drow和dcol主函数部分遍历每个源头判断边界条件
而唯一和dfs不一样的也只不过是dfs和bfs函数中的一小部分
class Solution {int m,n;vectorvectorbool record;int drow[4]{1,-1,0,0};int dcol[4]{0,0,1,-1};int ret;//与dfs一模一样typedef pairint,int ii;
public:void bfs(vectorvectorchar grid,int i,int j){queueii que;que.push({i,j});record[i][j]true;while(!que.empty()){auto [row,col]que.front();que.pop();for(int i0;i4;i){int newrowrowdrow[i];int newcolcoldcol[i];if(newrow0newrowmnewcol0newcolnrecord[newrow][newcol]falsegrid[newrow][newcol]1)//与dfs一模一样{que.push({newrow,newcol});record[newrow][newcol]true;}}}}int numIslands(vectorvectorchar grid) {mgrid.size();ngrid[0].size();record.resize(m,vectorbool(n));for(int i0;im;i){for(int j0;jn;j){if(record[i][j]falsegrid[i][j]1){bfs(grid,i,j);ret;}}}return ret;}//整个主函数也与dfs一模一样
};
所以bfs的公式也很明了和dfs大差不差
公式
class Solution {int dx[4] { 0,0,1,-1 };int dy[4] { 1,-1,0,0 };//方向数组vectorvectorbool record;//标记数组int m, n;//矩阵长宽typedef pairint, int ii;
public:void bfs(vectorvectorint grid, int i, int j){queueii que;//创建bfs用的队列que.push({ i , j });//将源头插入队列中while (!que.empty()){auto [row, col] que.front();//取队头元素for (int i 0; i 4; i){int nextrow row dy[i];int nextcol col dx[i];//新的坐标if (nextrow 0 nextrow m nextcol 0 nextcol n//不越界 record[nextrow][nextcol] false//没有走回头路 grid[nextrow][nextcol]...)//满足题目要求{record[nextrow][nextcol] true;que.push({ nextrow,nextcol });}}}}... main(vectorvectorint grid) {m grid.size();n grid[0].size();record.resize(m, vectorbool(n));//遍历每一个源头for (int i 0; i m; i){for (int j 0; j n; j){if (record[i][j]falsegrid[i][j] ! 0){record[i][j] true;bfs(grid, i, j);}}}}
};
