最短時間學會基于C++實現(xiàn)DFS深度優(yōu)先搜索
前言
同學們肯定或多或少的聽到過別人提起過DFS，BFS，卻一直都不太了解是什么，其實兩個各為搜索算法，常見使用 深度優(yōu)先搜索（DFS） 以及 廣度優(yōu)先搜索（BFS） ，今天我們就來講講什么是深度優(yōu)先搜索，深度優(yōu)先就是撞到了南墻才知道回頭，才會往上一層返回。
1.迷宮找出口,區(qū)分dfs,bfs：
dfs: 深度優(yōu)先我們可以看出他一次只往一個方向走,直到撞到了才會返回上一層去嘗試其他結果,圖片為上左下右的去走
BFS:廣度優(yōu)先就是嘗試該位置的旁邊的所有可能,再把所有可能的能走到的所有可能繼續(xù)走.撞到了就停止,如果全部可能都'碰壁'表示從該位置無法走到終點
對比兩個遍歷方式,相信大家有了初步的認識,讓我們接下來看看這道題
一、DFS經典放牌可能組合
題目：我們手上有編號為1~3的三個撲克牌，我們要放到編號為1 ~ 3的盒子當中，并且每個盒子中只放一張牌，問我們有多少種方法。
聰明的同學可能想一想就知道是6種了，但是當我們的要用計算機表達時我們要如何處理呢？題目雖簡單,所以我們借這道題來看看DFS如何解題.
方法一： 暴力循環(huán)，三層循環(huán)嵌套，判斷每張牌只用一次,這種方法簡單粗暴.
方法二： 深度搜索，我們選擇把按照從小到大的依次嘗試，在第一個盒子先開始放1，這時我們剩下兩張牌，對第二個盒子來說，我們從小到大放，放2，第三個盒子只有3了，第一種放法就出來了 1 2 3。
此時我們全部牌都放完了，然后我們這時候就是撞到了南墻了，我們就開始回收3，回收3的時候如果我們重復放3到第三個盒子就和之前重復了，所以我們再回收2，這時我們就可以把3放到第二個盒子，把2放在第三個盒子，第二種放法就出來了，1 3 2。
這時我們放完了之后再回收，我們回收了2，3后，1的所有可能我們就已經遍歷完了，這個時候我們就回收1，這時我們就可以開始把2放到第一個盒子，這時我們還有1 ，3 ，我們按之前的從小到大的原則，把1放入第二個盒子，剩一個3放在第三個盒子，這時的第三種放法 2 1 3出來了
同理我們收兩張牌就有組合2 3 1 ，同理3 1 2 ，2 31 ，這樣我們的6種出來了，即：我們站在一個盒子，我們按照我們手中的牌，從小到大依次嘗試，即我們有一個循環(huán)，從第一張牌開始
//處理第index個盒子 _ - - 并行遞歸，n有多大我們就調用多少次
DFS(vector<int>& box,int index,vector<int>& visited,int n)
{//box為盒子，index為當前盒子，visited為標記哪張牌用了的數(shù)組，n為處理幾張牌
if(index == n+1)//每一個盒子都有牌了
{
return;
}
for(int i =1;i<n;++i)
{
if(visited[i]==0)
{
//表示沒有用過的牌就可以放在當前的盒子當中
box[index] = i;//當前的盒子放這張牌
visited[i] =1 ;
//這里的邏輯就是我們站在一個盒子，我們按照我們手中的牌，從小到大依次嘗試
//到這里我們就處理下一個盒子
DFS(box,index+1,visited,n);
//一種方法完成，我們就回收牌
visited[i]=0;//標記成0就可以再次使用啦！
}
}
}
下面這個是測試n張牌，n個盒子的時候，我們所有的可能，可以自行粘貼復制到編輯器當中測試，請自行輸入n
void DFS(int index, int n, vector<int>& box, vector<int>& visited)
{
//處理當前的盒子
//我們這里打印看看每個盒子裝的都是什么
if (index == n + 1)
{
for (int i=1;i<box.size();++i)
cout << box[i] << " ";
cout << endl;
//表示每個盒子我們都已經放滿了東西，我們就可以返回上一層
return;
}
//每個盒子都要用n張牌來看看是否能夠使用，按照我們從小到大使用的規(guī)定原則
for (int i = 1; i <= n; ++i)
{
//表示牌沒有被用過，可以使用
if (visited[i] == 0)
{
box[index] = i;//表示在看到index個盒子的時候，我們用第i張牌放入
visited[i] = 1;//標記當前牌已經被使用
//走到這里我們當前這個盒子該干的事情已經干完了，我們就可以處理下一個盒子
DFS(index + 1, n, box, visited);
//表示所有的牌都已經放入并且返回，這時我們回收牌
visited[i] = 0;
}
}
}
int main()
{
int n;
vector<int> box;
vector<int> vistied;
cin >> n;
box.resize(n + 1, 0);
vistied.resize(n + 1, 0);
//這里的1是我們當前走到盒子，n是我們有多少牌，boxs是我們用來存放的盒子，
//visited是用來確定是否訪問過的標記矩陣
DFS(1, n, box, vistied);
return 0;
}
剛開始接觸DFS有時候會思考一些奇奇怪怪的問題,這個時候大家應該都去調試調試,一開始的問題一定是要解決的!!!
總結歸納：
深度優(yōu)先搜索的關鍵是解決當下應該怎么做，下一步的做法和當下的做法是一樣的。當下的做法如何做到嘗試每一種可能，我們用for循環(huán)遍歷，對于每一種可能的確定后，我們繼續(xù)下一步，當前的可能等到從下一步會退之后再處理
DFS常見的模型:
DFS(當前這一步的邏輯)
{
1.判斷邊界,是否已經撞到墻了:向上回退
2.嘗試當下的每一種可能
3.確定一種可能之后,繼續(xù)下一步,DFS(下一步)
}
二、leetcode 員工的重要性
/*
// Definition for Employee.
class Employee {
public:
int id;
int importance;
vector<int> subordinates;
};
*/
class Solution {
public:
int getImportance(vector<Employee*> employees, int id) {
}
};
題目的分析,題目給我們的信息就是給到一個id,要求他的直系下屬和直系下屬的直系下屬的importance(重要度),并且vector<Employee*> employees,給我們一個保存員工的數(shù)據(jù)結構,我們可以先將id和他的重要度綁定起來(哈希表um),這樣我們用DFS遍歷的時候,就可以先處理當前id,每一個id都要處理他的vector subordinates(這個是他的直系員工的id),再去遍歷當前id的直系下屬.
for(int id: um[id]->subordinates)
{
//對于當前我們需要sum加上加上當前id的重要度
sum += um[id]->importance;
//遍歷當前id的所有直系下屬
DFS(id,um,sum);
}
// 題目答案:
class Solution {
public:
void DFS(int id,unordered_map<int,Employee*>& um,int& sum)
{
//對于每一個id，下屬的id都會有屬于他們的vector<int> subordinates;
//所以我們都要去遍歷當前id的subordinates
for(int id: um[id]->subordinates)
{
//對于當前我們需要sum加上加上當前id的重要度
sum += um[id]->importance;
//遍歷當前id的直系下屬(**一路走到黑**),統(tǒng)計完的結果放到sum當中
DFS(id,um,sum);
}
}
int getImportance(vector<Employee*> employees, int id) {
//單個員工 id ，返回這個員工和他所有下屬的重要度之和。
//DFS:深度遍歷這個員工的旗下所有重要度之和，這題適合一條路走到黑
//因為在vector中的查找都是O（N）的時間復雜度，我們選擇用哈希表，并且將id與員工的指針建立映射,因為我們在DFS中要使用到用id找到員工
unordered_map<int,Employee*> um;
for(Employee* e : employees)
{
//將employees的數(shù)據(jù)導入us（哈希表中）
um[e->id] = e;
}
int sum = um[id]->importance;//提前加上當前id的重要度
//dfs是遍歷當前id的subordinates的重要度
DFS(id, um,sum);
return sum;
}
};
這道題之后實際上后面的題目也都是類似的，大家從這道題開始可以嘗試自己寫一寫，再看看我的代碼解析，這樣幫助理解！
三、leetcode 圖像渲染
這題實際上用bfs,dfs都可以,這里我們講的是dfs,所以我們用dfs的方式解決,一開始我的想法是,遍歷每一個位置的上下左右,將合法的位置并且是舊顏色的改成新顏色.
注：方向矩陣的概念：
int arr[4][2] ={{1,0},{0,1},{-1,0},{0,-1}};//方向矩陣
void DFS(vector<vector<int>>& image, int curX, int curY, int newColor,int row ,int col,int oldcolor)
{
image[curX][curY] = newColor;//上色
//遍歷 (sr，sc)的上下左右 -- 我們可以設置一個全局的方向矩陣
for(int i=0;i<4;++i)
{
//(newX,newY)就是該點的上下左右了
int newX = curX+arr[i][0];
int newY = curY+arr[i][1];
if(newX<0||newX>=row
||newY<0||newY>=col)
continue;//表示新的坐標越界了不符合要求，跳過
//走到這里表示新的坐標沒有問題,如果是就顏色我們就上色
if(image[newX][newY] == oldcolor)
{
//當前的點處理完，我們處理下一個點
DFS(image,newX,newY,newColor,row,col,oldcolor);
}
else
continue;
}
}
但是這樣子會有一個問題,當測試用例為新顏色和舊顏色相同的時候就會變成了死遞歸,所以我們少不了用標記矩陣,將我們走過的位置標記了他就不會重復走了。
以下為本道題的全部代碼
int arr[4][2] ={ { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
class Solution {
public:
void DFS(vector<vector<int>>& image, int curX, int curY, int newColor,vector<vector<int>>& visited,int row ,int col,int oldColor)
{
//給當前位置染色
image[curX][curY] = newColor;
//標記當前位置已經使用了
visited[curX][curY]=1;
//遍歷 (sr，sc)的上右下左 -- 我們可以設置一個全局的方向矩陣
for(int i=0;i<4;++i)
{
//(newX,newY)就是該點的上下左右了
int newX = curX+arr[i][0];
int newY = curY+arr[i][1];
//判斷新坐標是否合法
if(newX<0 || newX>=row
|| newY<0 || newY>=col)
continue;
//如果是沒有訪問過的并且是舊顏色就遞歸這個點的周圍
if(visited[newX][newY] == 0 &&
image[newX][newY] == oldColor)
DFS(image,newX,newY,newColor,visited,row,col,oldColor) ;
}
}
vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int newColor) {
//我們這道題也可以用BFS，DFS做都沒問題，我們這里講到DFS，所以就用DFS的思路解決
int row = image.size();
int col = image[0].size();
int oldColor =image[sr][sc];
//初始化標記矩陣，沒訪問過的置成0
vector<vector<int>> visited(row,vector<int>(col,0));
DFS(image,sr,sc,newColor,visited,row,col,oldColor);
return image;
}
};
四、leetcode 被圍繞的區(qū)域
本題就是想將全部沒有與外圍一圈O聯(lián)通的O換成X，與外界連通的O不做改變
思路：拿到這樣一道題，我們要將與外界O相連的O全部遍歷到，所以會用到深度優(yōu)先搜索，那么我們就可以從矩陣的外圍一圈（第一行，最后一行，第一列，最后一列）出發(fā)，將外圍的每一個O都深度搜索，將搜索到的O（即與外界相連的先換成#）
最后再將O換成#，將#換回O。當然也可以用標記矩陣來寫，都是可以的，這里兩種方法都寫出來看看
1.不使用標記矩陣
int arr[4][2] ={ { 0, 1 }, { 1, 0 }, { 0, -1 }, { -1, 0 } };
class Solution {
public:
void DFS(vector<vector<char>>& board,int row,int col,int curX,int curY)
{
//當前點就是聯(lián)通的‘O'
board[curX][curY] ='#';
for(int i =0;i<4;++i)
{
int newX = curX+arr[i][0];
int newY = curY+arr[i][1];
if(newX<0||newX>=row
||newY<0||newY>=col)
continue;
if(board[newX][newY]=='O')
DFS(board,row,col,newX,newY);
}
}
void solve(vector<vector<char>>& board) {
//我們可以從每一個邊界的O出發(fā)，鏈接的O就是不用改的，其他的都是要改成‘X'的
//但是我們可以通過修改與外面相連的O暫時修改#，就不需要標記矩陣了
int row =board.size();
int col=board[0].size();
for(int i=0;i<row;++i)
{
if(board[i][0] =='O')
DFS(board,row,col,i,0);
if(board[i][col-1] =='O')
DFS(board,row,col,i,col-1);
}
for(int j =0;j<col;++j)
{
if(board[0][j]=='O')
DFS(board,row,col,0,j);
if(board[row-1][j]=='O')
DFS(board,row,col,row-1,j);
}
for(int i =0;i<row;++i)
{
for(int j =0;j<col;++j)
{
if(board[i][j]=='O')
board[i][j]='X';
if(board[i][j]=='#')
board[i][j]='O';
}
}
return ;
}
};
2.使用標記矩陣
int arr[4][2]={{1,0},{0,1},{-1,0},{0,-1}};
class Solution {
public:
void DFS(vector<vector<int>>& visited,vector<vector<char>>& board,int row,int col,int curX ,int curY)
{
//與外界聯(lián)通的還是O，我們標記為1
visited[curX][curY] = 1;
for(int i =0;i<4;++i)
{
int newx = curX+arr[i][0];
int newy = curY+arr[i][1];
if(newx<0||newx>=row||
newy<0||newy>=col)
continue;
//沒有被訪問過的位置（防止重復遞歸）&& 為O的位置我們才遞歸
if(visited[newx][newy]==0&&
board[newx][newy]=='O')
{
DFS(visited,board,row,col,newx,newy);
}
}
}
void solve(vector<vector<char>>& board) {
//思路：我們從周圍的O出發(fā)，與邊界O DFS都能獲取到的位置我們都可以做個標記
//最后將標記的不動，沒標記的換成'X'(內陸)。
int row = board.size();
int col=board[0].size();
vector<vector<int>> visited(row,vector<int>(col,0));
//遍歷周圍為O的位置
//兩列
for(int i =0;i<row;++i)
{
if(board[i][0]=='O')
DFS(visited,board,row,col,i,0);
if(board[i][col-1]=='O')
DFS(visited,board,row,col,i,col-1);
}
//兩行
for(int j =0;j<col;++j)
{
if(board[0][j]=='O')
DFS(visited,board,row,col,0,j);
if(board[row-1][j]=='O')
DFS(visited,board,row,col,row-1,j);
}
//最后將沒有標記的O換成X，標記了的不變
for(int i =0;i<row;++i)
{
for(int j =0;j<col;++j)
{
if(visited[i][j]==0)
board[i][j] = 'X';
cout<<visited[i][j];
}
}
}
};
五、島嶼數(shù)量
有了前面題的基礎，對于這道題可謂是信手拈來，詳情請看注釋：
int arr[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
class Solution {
public:
void DFS(vector<vector<int>>& visited,vector<vector<char>>& grid,int row,int col,int curx,int cury)
{
//將當前位置標記為走過
visited[curx][cury]=1;
for(int i =0;i<4;++i)
{
int newx = curx+arr[i][0];
int newy = cury+arr[i][1];
if(newx<0||newx>=row||newy<0||newy>=col)
continue;
if(grid[newx][newy]=='1'&&visited[newx][newy]==0)
DFS(visited,grid,row,col,newx,newy);
}
}
int numIslands(vector<vector<char>>& grid) {
//這道題其實也是用BFS，DFS都可以解，用DFS的話我的思路是從第一個開始遍歷，遇到一個visited沒有訪問過的1就去遍歷他的上下左右，將他周圍的1都遍歷，在將次數(shù)加一
int row =grid.size();
int col=grid[0].size();
int count =0;
vector<vector<int>> visited(row,vector<int>(col,0));
for(int i =0;i<row;++i)
{
for(int j =0;j<col;++j)
{
if(visited[i][j]==0&&grid[i][j]=='1')
{
DFS(visited,grid,row,col,i,j);
count++;
}
}
}
return count;
}
};
六、 小練習：島嶼的最大面積
這道題留給大家作為一個小練習，有了前面的基礎，相信這道題想必不是問題?。?/p>
總結
回溯思想DFS一些難度較大的題一起講?。FS的學習時要注意多調試，想清楚了再下手寫，這樣往往能夠事半功倍
到此這篇關于最短時間學會基于C++實現(xiàn)DFS深度優(yōu)先搜索的文章就介紹到這了,更多相關C++ DFS深度優(yōu)先搜索內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
這篇文章主要介紹了C語言如何計算字符串長度問題，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2023-02-02
C++實現(xiàn)LeetCode(189.旋轉數(shù)組)
這篇文章主要介紹了C++實現(xiàn)LeetCode(189.旋轉數(shù)組),本篇文章通過簡要的案例,講解了該項技術的了解與使用,以下就是詳細內容,需要的朋友可以參考下2021-07-07
下面小編就為大家?guī)硪黄獪\談c++中的while(cin)問題。小編覺得挺不錯的，現(xiàn)在就分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2017-05-05
這篇文章主要介紹了C++命名空間實例詳解，有感興趣的同學可以研究下2021-02-02
這篇文章主要為大家介紹了c語言實現(xiàn)學生管理系統(tǒng)，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助<BR>2021-12-12
this 指針在C++類和對象中是個很方便實用的關鍵字，可以簡化對象成員屬性的調用，使代碼表達的含義更加準確；在之前的學習中我們都可以判斷變量所占內存空間大小，那么我們創(chuàng)建的類對象所占的內存空間怎么計算呢?想知道this的妙用和類對象占用的內存空間就來跟我學習吧2022-06-06
本篇文章是對C++中的Data Member內存布局進行了詳細的分析介紹，需要的朋友參考下2013-07-07
VC++ loadlibrary()加載三方dll失敗, 返回錯誤碼:126的解決方法
今天在編寫VC++ loadlibrary()加載三方dll是總是失敗,并且返回錯誤碼:126，這里就為大家分享一下具體的解決方法2021-03-03
這篇文章主要介紹了Codec2解碼組件，本文給大家介紹的非常詳細，對大家的學習或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-09-09
這篇文章主要介紹了C語言實現(xiàn)成績統(tǒng)計示例，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-11-11