搜索算法（一） 深度优先搜索 dfs

一、搜索算法

包括深度优先搜索算法和广度优先搜索算法，用于树或图等结构中进行搜索。

二、深度优先搜索

深度优先算法会尽可能深地搜索树的分支。当节点v的所在边都己被探寻过，搜索将回溯到发现节点v的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。

 维基百科上的伪代码：

 简单来说，就是沿着起始节点一直向节点的子节点，子节点的子节点……一直向最深处（叶子节点）搜索，若搜索到最深处（下一个节点为空），还未找到目标，则返回上一级节点，寻找该节点的另一个子节点，再继续这个过程。

实现方法：栈或者递归

• 栈的优点：不会出现递归栈满的情况，开销小
• 递归的优点：代码方便实现，方便回溯

三、DFS练习题

1）

力扣https://leetcode.cn/problems/max-area-of-island/submissions/

栈实现：

利用栈完成对岛屿周围坐标的搜索

class Solution {
public:int maxAreaOfIsland(vector<vector<int>>& grid) {if(grid.size()==0 || grid[0].size()==0) return 0;int m = grid.size(), n = grid[0].size();int maxArea = 0, area;stack<pair<int,int>> st;vector<vector<bool>> visited(m,vector<bool>(n,false));vector<int> p = {-1,0,1,0,-1};int x,y;for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(grid[i][j]==1 && visited[i][j]==false){visited[i][j] = true;area = 1;st.push({i,j});while(!st.empty()){auto t = st.top();st.pop();for(int i=0;i<4;i++){x = t.first + p[i];y = t.second + p[i+1];
if(x>=0 && x<m && y>=0 && y<n && grid[x][y]==1 && visited[x][y]==false){visited[x][y] = true;area += 1;st.push({x,y});
}}}maxArea = max(maxArea, area);}}}return maxArea;}};

递归实现：

主函数遍历所有搜索位置，决定是否开始搜索（是否为岛屿，是否已经访问过）

辅函数负责深度优先搜索的递归调用（遍历上下左右四个节点，若四个节点为岛屿且未被访问，则继续递归调用辅函数）

class Solution {
public:int maxAreaOfIsland(vector<vector<int>>& grid) {if(grid.size()==0 || grid[0].size()==0) return 0;int m = grid.size(), n = grid[0].size();int maxArea = 0;vector<vector<bool>> visited(m,vector<bool>(n,false));for(int i=0;i<m;i++){for(int j=0;j<n;j++){if(grid[i][j]==1 && visited[i][j]==false){visited[i][j] = true;int area = 1 + dfs(grid,visited,i,j);maxArea = max(maxArea, area);}}}return maxArea;}int dfs(vector<vector<int>>& grid, vector<vector<bool>>& visited, int a, int b){static const int x[4] = {0,0,1,-1};static const int y[4] = {1,-1,0,0};int res = 0;int m = grid.size(), n = grid[0].size();for(int i=0;i<4;i++){int p = a + x[i];int q = b + y[i];if(p>=0 && q>=0 && p<m && q<n && grid[p][q]==1 && visited[p][q]==false){visited[p][q] = true;res += 1 + dfs(grid,visited,p,q);}}return res;}};