最短時間學(xué)會基于C++實現(xiàn)DFS深度優(yōu)先搜索

更新時間：2021年08月23日 10:35:06 作者：^jhao^

常見使用深度優(yōu)先搜索(DFS)以及廣度優(yōu)先搜索(BFS)這兩種搜索，今天我們就來講講什么是深度優(yōu)先搜索，感興趣的可以了解一下

前言

同學(xué)們肯定或多或少的聽到過別人提起過DFS，BFS，卻一直都不太了解是什么，其實兩個各為搜索算法，常見使用深度優(yōu)先搜索（DFS）以及廣度優(yōu)先搜索（BFS），今天我們就來講講什么是深度優(yōu)先搜索，深度優(yōu)先就是撞到了南墻才知道回頭，才會往上一層返回。

1.迷宮找出口,區(qū)分dfs,bfs：

dfs: 深度優(yōu)先我們可以看出他一次只往一個方向走,直到撞到了才會返回上一層去嘗試其他結(jié)果,圖片為上左下右的去走

請?zhí)砑訄D片描述

BFS:廣度優(yōu)先就是嘗試該位置的旁邊的所有可能,再把所有可能的能走到的所有可能繼續(xù)走.撞到了就停止,如果全部可能都'碰壁'表示從該位置無法走到終點

在這里插入圖片描述

對比兩個遍歷方式,相信大家有了初步的認(rèn)識,讓我們接下來看看這道題

一、DFS經(jīng)典放牌可能組合

題目：我們手上有編號為1~3的三個撲克牌，我們要放到編號為1 ~ 3的盒子當(dāng)中，并且每個盒子中只放一張牌，問我們有多少種方法。

聰明的同學(xué)可能想一想就知道是6種了，但是當(dāng)我們的要用計算機(jī)表達(dá)時我們要如何處理呢？題目雖簡單,所以我們借這道題來看看DFS如何解題.

方法一：暴力循環(huán)，三層循環(huán)嵌套，判斷每張牌只用一次,這種方法簡單粗暴.

方法二：深度搜索，我們選擇把按照從小到大的依次嘗試，在第一個盒子先開始放1，這時我們剩下兩張牌，對第二個盒子來說，我們從小到大放，放2，第三個盒子只有3了，第一種放法就出來了 1 2 3。
此時我們?nèi)颗贫挤磐炅?，然后我們這時候就是撞到了南墻了，我們就開始回收3，回收3的時候如果我們重復(fù)放3到第三個盒子就和之前重復(fù)了，所以我們再回收2，這時我們就可以把3放到第二個盒子，把2放在第三個盒子，第二種放法就出來了，1 3 2。

這時我們放完了之后再回收，我們回收了2，3后，1的所有可能我們就已經(jīng)遍歷完了，這個時候我們就回收1，這時我們就可以開始把2放到第一個盒子，這時我們還有1 ，3 ，我們按之前的從小到大的原則，把1放入第二個盒子，剩一個3放在第三個盒子，這時的第三種放法 2 1 3出來了

同理我們收兩張牌就有組合2 3 1 ，同理3 1 2 ，2 31 ，這樣我們的6種出來了，即：我們站在一個盒子，我們按照我們手中的牌，從小到大依次嘗試，即我們有一個循環(huán)，從第一張牌開始

//處理第index個盒子 _ - - 并行遞歸，n有多大我們就調(diào)用多少次
DFS(vector<int>& box,int index,vector<int>& visited,int n)
{//box為盒子，index為當(dāng)前盒子，visited為標(biāo)記哪張牌用了的數(shù)組，n為處理幾張牌
	if(index == n+1)//每一個盒子都有牌了
	{
		return;
	}
	for(int i =1;i<n;++i)
	{
		if(visited[i]==0)
		{
			//表示沒有用過的牌就可以放在當(dāng)前的盒子當(dāng)中
			box[index] = i;//當(dāng)前的盒子放這張牌
			visited[i] =1 ;
			//這里的邏輯就是我們站在一個盒子，我們按照我們手中的牌，從小到大依次嘗試
			//到這里我們就處理下一個盒子
			DFS(box,index+1,visited,n);
			//一種方法完成，我們就回收牌
			visited[i]=0;//標(biāo)記成0就可以再次使用啦！
		}
	}
}

下面這個是測試n張牌，n個盒子的時候，我們所有的可能，可以自行粘貼復(fù)制到編輯器當(dāng)中測試，請自行輸入n

void DFS(int index, int n, vector<int>& box, vector<int>& visited)
{
	//處理當(dāng)前的盒子

	//我們這里打印看看每個盒子裝的都是什么
	if (index == n + 1)
	{
		for (int i=1;i<box.size();++i)
			cout << box[i] << " ";
		cout << endl;
		
		//表示每個盒子我們都已經(jīng)放滿了東西，我們就可以返回上一層
		return;
	}

	//每個盒子都要用n張牌來看看是否能夠使用，按照我們從小到大使用的規(guī)定原則
	for (int i = 1; i <= n; ++i)
	{
		//表示牌沒有被用過，可以使用
		if (visited[i] == 0)
		{
			box[index] = i;//表示在看到index個盒子的時候，我們用第i張牌放入
			
			visited[i] = 1;//標(biāo)記當(dāng)前牌已經(jīng)被使用
			//走到這里我們當(dāng)前這個盒子該干的事情已經(jīng)干完了，我們就可以處理下一個盒子

			DFS(index + 1, n, box, visited);
			//表示所有的牌都已經(jīng)放入并且返回，這時我們回收牌
			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是我們當(dāng)前走到盒子，n是我們有多少牌，boxs是我們用來存放的盒子，	
	//visited是用來確定是否訪問過的標(biāo)記矩陣
	DFS(1, n, box, vistied);
	return 0;
}

在這里插入圖片描述

剛開始接觸DFS有時候會思考一些奇奇怪怪的問題,這個時候大家應(yīng)該都去調(diào)試調(diào)試,一開始的問題一定是要解決的!!!

總結(jié)歸納：
深度優(yōu)先搜索的關(guān)鍵是解決當(dāng)下應(yīng)該怎么做，下一步的做法和當(dāng)下的做法是一樣的。當(dāng)下的做法如何做到嘗試每一種可能，我們用for循環(huán)遍歷，對于每一種可能的確定后，我們繼續(xù)下一步，當(dāng)前的可能等到從下一步會退之后再處理
DFS常見的模型:
DFS(當(dāng)前這一步的邏輯)
{
1.判斷邊界,是否已經(jīng)撞到墻了:向上回退
2.嘗試當(dāng)下的每一種可能
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ù)結(jié)構(gòu),我們可以先將id和他的重要度綁定起來(哈希表um),這樣我們用DFS遍歷的時候,就可以先處理當(dāng)前id,每一個id都要處理他的vector subordinates(這個是他的直系員工的id),再去遍歷當(dāng)前id的直系下屬.

for(int id: um[id]->subordinates)
        {
            //對于當(dāng)前我們需要sum加上加上當(dāng)前id的重要度
            sum += um[id]->importance;
            //遍歷當(dāng)前id的所有直系下屬
            DFS(id,um,sum);
        }

在這里插入圖片描述

// 題目答案:
class Solution {
public: 
    void DFS(int id,unordered_map<int,Employee*>& um,int& sum)
    {
        //對于每一個id，下屬的id都會有屬于他們的vector<int> subordinates;
        //所以我們都要去遍歷當(dāng)前id的subordinates
        for(int id: um[id]->subordinates)
        {
            //對于當(dāng)前我們需要sum加上加上當(dāng)前id的重要度
            sum += um[id]->importance;
            //遍歷當(dāng)前id的直系下屬(**一路走到黑**),統(tǒng)計完的結(jié)果放到sum當(dāng)中
            DFS(id,um,sum);
        }
    }
    
    int getImportance(vector<Employee*> employees, int id) {
        //單個員工 id ，返回這個員工和他所有下屬的重要度之和。
        //DFS:深度遍歷這個員工的旗下所有重要度之和，這題適合一條路走到黑
        //因為在vector中的查找都是O（N）的時間復(fù)雜度，我們選擇用哈希表，并且將id與員工的指針建立映射,因為我們在DFS中要使用到用id找到員工
        unordered_map<int,Employee*> um;
        for(Employee* e : employees)
        {
            //將employees的數(shù)據(jù)導(dǎo)入us（哈希表中）
            um[e->id] = e;
        }
        int sum = um[id]->importance;//提前加上當(dāng)前id的重要度
        //dfs是遍歷當(dāng)前id的subordinates的重要度
        DFS(id, um,sum);
        return sum;
    }
};

這道題之后實際上后面的題目也都是類似的，大家從這道題開始可以嘗試自己寫一寫，再看看我的代碼解析，這樣幫助理解！

三、leetcode 圖像渲染

733. 圖像渲染

這題實際上用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)的上下左右 -- 我們可以設(shè)置一個全局的方向矩陣
        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;//表示新的坐標(biāo)越界了不符合要求，跳過
            
            //走到這里表示新的坐標(biāo)沒有問題,如果是就顏色我們就上色
            if(image[newX][newY] == oldcolor)
            {     
                //當(dāng)前的點處理完，我們處理下一個點
                DFS(image,newX,newY,newColor,row,col,oldcolor);
            }
            else
            continue;        
        }
    }

但是這樣子會有一個問題,當(dāng)測試用例為新顏色和舊顏色相同的時候就會變成了死遞歸,所以我們少不了用標(biāo)記矩陣,將我們走過的位置標(biāo)記了他就不會重復(fù)走了。

在這里插入圖片描述

以下為本道題的全部代碼

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)
    {
        //給當(dāng)前位置染色
         image[curX][curY] = newColor;
         //標(biāo)記當(dāng)前位置已經(jīng)使用了
         visited[curX][curY]=1;

        
        //遍歷 (sr，sc)的上右下左 -- 我們可以設(shè)置一個全局的方向矩陣
        for(int i=0;i<4;++i)
        {
            //(newX,newY)就是該點的上下左右了
            int newX = curX+arr[i][0];
            int newY = curY+arr[i][1];
            //判斷新坐標(biāo)是否合法
            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];
        //初始化標(biāo)記矩陣，沒訪問過的置成0
        vector<vector<int>> visited(row,vector<int>(col,0));
        DFS(image,sr,sc,newColor,visited,row,col,oldColor);
        return image;
    }
};

四、leetcode 被圍繞的區(qū)域

130. 被圍繞的區(qū)域

在這里插入圖片描述

本題就是想將全部沒有與外圍一圈O聯(lián)通的O換成X，與外界連通的O不做改變
思路：拿到這樣一道題，我們要將與外界O相連的O全部遍歷到，所以會用到深度優(yōu)先搜索，那么我們就可以從矩陣的外圍一圈（第一行，最后一行，第一列，最后一列）出發(fā)，將外圍的每一個O都深度搜索，將搜索到的O（即與外界相連的先換成#）
最后再將O換成#，將#換回O。當(dāng)然也可以用標(biāo)記矩陣來寫，都是可以的，這里兩種方法都寫出來看看

1.不使用標(biāo)記矩陣

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)
    {
        //當(dāng)前點就是聯(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暫時修改#，就不需要標(biā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.使用標(biāo)記矩陣

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，我們標(biā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;
            //沒有被訪問過的位置（防止重復(fù)遞歸）&& 為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都能獲取到的位置我們都可以做個標(biāo)記
        //最后將標(biāo)記的不動，沒標(biāo)記的換成'X'(內(nèi)陸)。
        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);    
        }
        //最后將沒有標(biāo)記的O換成X，標(biāo)記了的不變
        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ù)量

200. 島嶼數(shù)量

在這里插入圖片描述

有了前面題的基礎(chǔ)，對于這道題可謂是信手拈來，詳情請看注釋：

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)
    {
        //將當(dāng)前位置標(biāo)記為走過
        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;
    }
};