DFS与BFS LeetCode 刷题小结(一)
本节我们将汇总一些 LeetCode bfs与dfs相关的题。
关于深度优先搜索(DFS)和广度优先搜索(BFS)，在往期博客中有所介绍，本节我们将介绍其他典题。
朋友圈
班上有 N 名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。
给定一个 N * N 的矩阵 M，表示班级中学生之间的朋友关系。如果M[i][j] = 1，表示已知第 i 个和 j 个学生互为朋友关系，否则为不知道。你必须输出所有学生中的已知的朋友圈总数。
来源：https://leetcode-cn.com/problems/friend-circles
image.png
给出的数据是一个图的邻接矩阵，求得是该图无向图连通块的个数，对于这类问题，bfs和dfs都可以解决。
DFS版
我们需要一个vist来保存节点状态：
vector<bool> vist(M.size(),false);
当我们访问一个节点时，访问与它相邻的节点，再访问这个节点的相邻节点，直到访问到“底”，每访问一个节点改变它的状态，当遍历到没有访问的相邻节点时，回溯之前的节点继续访问。
程序如下：
class Solution {
public:
int findCircleNum(vector<vector<int>>& M) {
int len =M.size();
vector<bool> vist(len,false);
int res =0;
for(int i=0;i<len;i++){
if(!vist[i]){
dfs(M,vist,i);
res++;
}
}
return res;
}
void dfs(vector<vector<int>>& M,vector<bool>& vist,int i){
for(int j=0;j<M.size();j++){
if(M[i][j]==1&&!vist[j]){
vist[j]=true;
dfs(M,vist,j);
}
}
}
};
BFS版
广度优先就是一层层地来，类似于树的层次遍历，需要用到队列保存每层节点，如果对树的层序遍历很熟悉，那图的广度优先搜索也就不难了。
程序如下：
class Solution {
public:
int findCircleNum(vector<vector<int>>& M) {
int len = M.size();
int res=0;
vector<bool> vist(len,false);
queue<int> q;
for(int i=0;i<len;i++){
if(!vist[i]){
q.push(i);
while(!q.empty()){
int cur = q.front();
q.pop();
vist[cur]=true;
for(int j=0;j<len;j++){
if(M[cur][j]==1&&!vist[j]){
q.push(j);
}
}
}
res++;
}
}
return res;
}
};
这个题还有一种做法是并查集，本节我们暂不讲述，在之后的章节会汇总并查集有关的题。
岛屿数量
给定一个由 '1'（陆地）和 '0'（水）组成的的二维网格，计算岛屿的数量。一个岛被水包围，并且它是通过水平方向或垂直方向上相邻的陆地连接而成的。你可以假设网格的四个边均被水包围。
来源：https://leetcode-cn.com/problems/number-of-islands
image.png
这个题的思路和上面题类似，需要注意的地方便是处理的对象略有不同，上题是邻接矩阵，来看具体的细节吧。
DFS版
如果一个区域块是1，是一块陆地，我们要找到与它相邻的1，在不越界的情况下，该块上下左右若为1，则递归该块继续判断其上下左右块，如果递归结束了，意味着是一块陆地，因为一块陆地的任意两个点明显是可达的（通过上下左右移动），在递归时，每到为1的块，该块置零。
程序如下：
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int rows = grid.size();
if(rows==0){
return 0;
}
int lists = grid[0].size();
int lands = 0;
for(int i=0;i<rows;i++){
for(int j=0;j<lists;j++){
if(grid[i][j]=='1'){
lands++;
dfs(grid,i,j);
}
}
}
return lands;
}
void dfs(vector<vector<char>>& grid,int i,int j){
int rows=grid.size();
int lists=grid[0].size();
grid[i][j]='0';
if(i>=1 && grid[i-1][j]=='1'){
dfs(grid,i-1,j);
}
if(i<rows-1 && grid[i+1][j]=='1'){
dfs(grid,i+1,j);
}
if(j>=1 && grid[i][j-1]=='1'){
dfs(grid,i,j-1);
}
if(j<lists-1&&grid[i][j+1]=='1'){
dfs(grid,i,j+1);
}
}
};
BFS版
BFS版其实也大同小异，当处于陆地块时，该块置零，用一个队列保存其上下左右的陆地块，对于队列里面的块，在不越界的情况下判断其上下左右，为1的块入队列，同时赋0。
程序如下：
class Solution {
public:
int numIslands(vector<vector<char>>& grid) {
int rows= grid.size();
if(rows==0){
return 0;
}
int lists=grid[0].size();
int lands=0;
for(int i=0;i<rows;i++){
for(int j=0;j<lists;j++){
if(grid[i][j]=='1'){
lands++;
grid[i][j]='0';
queue<pair<int,int>> point;
point.push({i,j});
while(!point.empty()){
auto cur = point.front();
point.pop();
int i_=cur.first;
int j_=cur.second;
if(i_>=1 && grid[i_-1][j_]=='1'){
point.push({i_-1,j_});
grid[i_-1][j_]='0';
}
if(i_<rows-1 && grid[i_+1][j_]=='1'){
point.push({i_+1,j_});
grid[i_+1][j_]='0';
}
if(j_>=1 && grid[i_][j_-1]=='1'){
point.push({i_,j_-1});
grid[i_][j_-1]='0';
}
if(j_<lists-1 && grid[i_][j_+1]=='1'){
point.push({i_,j_+1});
grid[i_][j_+1]='0';
}
}
}
}
}
return lands;
}
};
最后来看一道bfs的题。
腐烂的橘子
在给定的网格中，每个单元格可以有以下三个值之一：
值 0 代表空单元格；
值 1 代表新鲜橘子；
值 2 代表腐烂的橘子。
每分钟，任何与腐烂的橘子（在 4 个正方向上）相邻的新鲜橘子都会腐烂。
返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1。
来源：https://leetcode-cn.com/problems/rotting-oranges
image.png
这个题很明显使用广度优先搜索，从烂橘子出发，在不越界的情况下，其上下左右的橘子都会烂掉，计时，统计这个过程烂掉的橘子数，若等于原始好的橘子数，返回时间，否则为-1。
程序如下：
class Solution {
public:
int orangesRotting(vector<vector<int>>& grid) {
int min=0,fresh=0;
queue<pair<int,int>> q;
for(int i=0;i<grid.size();i++){
for(int j=0;j<grid[0].size();j++){
if(grid[i][j]==1){
//新鲜橘子
fresh++;
}else if(grid[i][j]==2){
//腐烂的橘子
q.push({i,j});
}
}
}
vector<pair<int,int>> dirs={{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
while(!q.empty()){
int n=q.size();
bool sign=false;
while(n--){
auto point=q.front();
q.pop();
for(auto cur : dirs){
int i=point.first+cur.first;
int j=point.second+cur.second;
if(i>=0&&i<grid.size()&&j>=0&&j<grid[0].size()&&grid[i][j]==1){
grid[i][j]=2;
q.push({i,j});
fresh--;
sign=true;
}
}
}
if(sign){
min++;
}
}
return fresh?-1:min;
}
};
本节内容暂告一段落，之后将继续更新。
