本節(jié)我們將匯總一些 LeetCode bfs與dfs相關的題。
關于深度優(yōu)先搜索(DFS)和廣度優(yōu)先搜索(BFS)苦酱，在往期博客中有所介紹，本節(jié)我們將介紹其他典題。
朋友圈
班上有 N 名學生库物。其中有些人是朋友，有些則不是贷帮。他們的友誼具有是傳遞性戚揭。如果已知 A 是 B 的朋友，B 是 C 的朋友撵枢，那么我們可以認為 A 也是 C 的朋友民晒。所謂的朋友圈，是指所有朋友的集合锄禽。
給定一個 N * N 的矩陣 M潜必，表示班級中學生之間的朋友關系。如果M[i][j] = 1沟绪，表示已知第 i 個和 j 個學生互為朋友關系刮便，否則為不知道。你必須輸出所有學生中的已知的朋友圈總數(shù)绽慈。
來源：https://leetcode-cn.com/problems/friend-circles
給出的數(shù)據(jù)是一個圖的鄰接矩陣恨旱，求得是該圖無向圖連通塊的個數(shù)，對于這類問題坝疼，bfs和dfs都可以解決搜贤。
DFS版
我們需要一個vist來保存節(jié)點狀態(tài)：
vector<bool> vist(M.size(),false);
當我們訪問一個節(jié)點時，訪問與它相鄰的節(jié)點钝凶，再訪問這個節(jié)點的相鄰節(jié)點仪芒，直到訪問到“底”唁影，每訪問一個節(jié)點改變它的狀態(tài)，當遍歷到?jīng)]有訪問的相鄰節(jié)點時掂名，回溯之前的節(jié)點繼續(xù)訪問据沈。
程序如下：
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版
廣度優(yōu)先就是一層層地來，類似于樹的層次遍歷饺蔑，需要用到隊列保存每層節(jié)點锌介，如果對樹的層序遍歷很熟悉，那圖的廣度優(yōu)先搜索也就不難了猾警。
程序如下：
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;
}
};
這個題還有一種做法是并查集孔祸，本節(jié)我們暫不講述，在之后的章節(jié)會匯總并查集有關的題发皿。
島嶼數(shù)量
給定一個由 '1'（陸地）和 '0'（水）組成的的二維網(wǎng)格崔慧，計算島嶼的數(shù)量。一個島被水包圍穴墅，并且它是通過水平方向或垂直方向上相鄰的陸地連接而成的惶室。你可以假設網(wǎng)格的四個邊均被水包圍。
來源：https://leetcode-cn.com/problems/number-of-islands
這個題的思路和上面題類似封救，需要注意的地方便是處理的對象略有不同拇涤，上題是鄰接矩陣，來看具體的細節(jié)吧誉结。
DFS版
如果一個區(qū)域塊是1鹅士，是一塊陸地，我們要找到與它相鄰的1惩坑，在不越界的情況下掉盅，該塊上下左右若為1，則遞歸該塊繼續(xù)判斷其上下左右塊以舒，如果遞歸結束了趾痘，意味著是一塊陸地，因為一塊陸地的任意兩個點明顯是可達的（通過上下左右移動）蔓钟，在遞歸時永票，每到為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的題。
腐爛的橘子
在給定的網(wǎng)格中瓢阴，每個單元格可以有以下三個值之一：
值 0 代表空單元格畅蹂；
值 1 代表新鮮橘子；
值 2 代表腐爛的橘子荣恐。
每分鐘魁莉，任何與腐爛的橘子（在 4 個正方向上）相鄰的新鮮橘子都會腐爛。
返回直到單元格中沒有新鮮橘子為止所必須經(jīng)過的最小分鐘數(shù)募胃。如果不可能，返回 -1畦浓。
來源：https://leetcode-cn.com/problems/rotting-oranges
這個題很明顯使用廣度優(yōu)先搜索痹束，從爛橘子出發(fā)，在不越界的情況下讶请，其上下左右的橘子都會爛掉祷嘶，計時，統(tǒng)計這個過程爛掉的橘子數(shù)夺溢，若等于原始好的橘子數(shù)论巍，返回時間，否則為-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;
}
};
本節(jié)內容暫告一段落嘉汰，之后將繼續(xù)更新。
