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

一、���索算法

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

二、深度优先搜索

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

 维基百科上的伪代码：

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

实现方法：栈或者递归

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

  三、DFS练习题

  1）

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

  栈实现：

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

  class Solution {public:    int maxAreaOfIsland(vector& grid) {        if(grid.size()==0 || grid[0].size()==0) return 0;        int m = grid.size(), n = grid[0].size();        int maxArea = 0, area;        stack st;        vector visited(m,vector(n,false));        vector p = {-1,0,1,0,-1};        int x,y;        for(int i=0;i