搜索算法深度优先搜索

目录一、通过下面一个问题总结深度优先搜索1、深度优先搜索的一般步骤2、深度优先搜索的特点3、深度优先搜索的代码实现二、例题分析1、员工重要性2、图像渲染3、岛屿的周

目录

一、通过下面一个问题总结深度优先搜索

1、深度优先搜索的一般步骤

2、深度优先搜索的特点

3、深度优先搜索的代码实现

二、例题分析

1、员工重要性

2、图像渲染

3、岛屿的周长

4、被围绕的区域

5、岛屿数量

6、岛屿最大面积

---

一、通过下面一个问题总结深度优先搜索

问题：有编号为1~3的三张牌和编号为1~3的三个盒子，将三张牌放到三个盒子中且每个盒子只能放一张牌，问：一共有多少种方法？

• 根据题意，每个盒子放的牌有三种可能（1号盒子放的牌可能是1、2或3，2号...）。假定，从1号盒子开始放，接着放2号、3号。
• 给1号盒子放牌时，由于1号盒子是第一个放的，因此有三种选择：1、2、3号牌。假定，第一次放入1号牌，第二次放入2号牌...
• 给2号盒子放牌，此时1号盒子已经放入了1号牌，因此2号盒子只能从2、3号盒子选一张牌放入，假定选2号牌放入。
• 给3号盒子放牌，此时只剩下3号牌还没有放入，因此3号盒子放入3号牌。
• 继续往后走，已经没有盒子也没有牌了，也就是说一种方法已经完成。此时，需要折返，找另外一种方法。
• 折返到3号盒子，拿出三号盒子中的牌，此时只有3号牌没被放入，但是3号牌已经在3号盒子放入过一次，不能再次放入，因此继续折返。
• 折返到2号盒子，拿出2号盒子中的牌，此时有2、3号牌没有放入，可以将3号牌放入2号盒子，继续往后走，将2号牌放入3号盒子。
• 在继续走，后边又没有盒子了，第2中方法完成。继续折返...依此类推，直到找到所有方法。

代码实现：

void DFS(int index, std::vector box, std::vector brand){//边界处理if (index == box.size()){//打印for (int i = 1; i 1、深度优先搜索的一般步骤

分析问题，找出问题的一般规律。

按照某一特定路线进行搜索。

判断是否到达搜索边界，如果到达则折返进行搜索，否则继续进行深度优先搜索。

输出结果

Dfs(当前这一步的处理逻辑){1. 判断边界，是否已经一条道走到黑了：向上回退2. 尝试当下的每一种可能3. 确定一种可能之后，继续下一步 Dfs(下一步)}

2、深度优先搜索的特点

• 深度优先搜索（DFS,Depth First Serach）算法是一种方法尝试结束，在折返尝试另一种方法。
• 深度优先搜索一般采用递归实现

3、深度优先搜索的代码实现

处理当前状态

处理下一个状态

折返

边界处理

注意：深度优先搜索算法一般采用递归实现，处理边界是解决问题的关键。

二、例题分析

1、员工重要性

根据题目可以看出这是一个典型的深度优先搜索的题目。例如：[[1, 5, [2, 3]], [2, 3, [4,5]], [3, 3, [6]]，[4，2，[]]，[5,2，[7]],[6,3，[]],[7,1，[]]], 1

搜索顺序：1->2->4->5->->3->6

临界条件：当某一条路径走到头了，就需要折返，很明显在这里某一个节点的subordinates为NULL时就该折返了。即employees[i]->subordinates.empty()。

代码描述：

class Solution {public:void _getImportance(vectorfor(int i = 0;i id == id){ret += employees[i]->importance;index = i;}}//临界if((employees[index]->subordinates).empty())return;//处理下一个状态for(int i = 0;i subordinates).size();i++)_getImportance(employees,(employees[index]->subordinates)[i],ret);}int getImportance(vector employees, int id) {int ret = 0;_getImportance(employees,id,ret);return ret; }};

2、图像渲染

思路：深度优先搜索

从当前像素点开始渲染，渲染完后继续渲染上下左右方向的像素点。在使用递归时，结束条件有两个：坐标非法；颜色和原始颜色不同（不需要渲染）。

注意：出递归，所以有可能存在渲染完成后和渲染之前是一样的（新颜色和就颜色相同），就有可能导致无法退每渲染完一个像素点，在原始图画上将该位置标记为-1（像素值为0~65535，只要不在这范围都可以），使用一个新的数组保存渲染后的图像。

class Solution {public:void _floodFill(vector}if(img[src][sc] != oldColor){//与初始颜色不同return;}//进行渲染img[src][sc] = -1;ret[src][sc] = newColor;//依次从上下左右四个方向进行渲染_floodFill(img,ret,src-1,sc,oldColor,newColor);_floodFill(img,ret,src+1,sc,oldColor,newColor);_floodFill(img,ret,src,sc-1,oldColor,newColor);_floodFill(img,ret,src,sc+1,oldColor,newColor);}vector floodFill(vector_floodFill(image,ret,sr,sc,image[sr][sc],newColor);return ret;}};

3、岛屿的周长

class Solution {public:void _islandPerimeter(vectorif((sr-1 >= 0 }else if((sr-1 = grid.size()) ||grid[sr-1][sc] != -1){ret += 1;}//下if(sr+1 >= 0 }else if((sr+1 = grid.size()) || grid[sr+1][sc] != -1){ret += 1;}//左if(sc-1 >= 0 }else if((sc-1 = grid[0].size()) || grid[sr][sc-1] != -1){ret += 1;}//右if(sc+1 >= 0 }else if((sc+1 = grid[0].size()) || grid[sr][sc+1] != -1){ret += 1;}}int islandPerimeter(vectorint col = grid[0].size();for(int i = 0;i 4、被围绕的区域

思路：如果直接找被围绕的岛屿，则终止条件应该是：所给坐标为边界或者与边界相连，边界问题很难处理。因此，将问题转化成先将边界和边界相连的岛屿变成Y，在将其他的所有O变成X，最后再将Y变成O。也就是说，使用深度优先搜索处理边界为X及与边界上X相连的X。

class Solution {public:void _solve(vectorif(board[sr][sc] != O)return;//变成Y是O进行扩散board[sr][sc] = Y;_solve(board,sr-1,sc);_solve(board,sr+1,sc);_solve(board,sr,sc-1);_solve(board,sr,sc+1);}void solve(vectori 5、岛屿数量

思路：对每一块岛屿进行渲染，渲染的次数就是岛屿的数量。进行渲染时，采用深度优先搜索，统计次数：采用双循环对数组济宁遍历，如果是1就开始进行渲染并且渲染次数+1

class Solution {public:void _numIslands(vectorif(grid[sr][sc] != 1)return;//将其变成0grid[sr][sc] = 0;//其他四个方向搜索_numIslands(grid,sr-1,sc);_numIslands(grid,sr+1,sc);_numIslands(grid,sr,sc-1);_numIslands(grid,sr,sc+1);}int numIslands(vectorfor(int i = 0;i 6、岛屿最大面积

思路：首先对每块陆地进行渲染，在渲染时统计面积。对于该数组中所有的陆地，都济宁渲染，每次渲染时找出最大的面积的岛屿。

class Solution {public:void _maxAreaOfIsland(vectorif(grid[sr][sc] != 1)return;//进行渲染并计算面积grid[sr][sc] = 0;area++;//其他四个方向搜索_maxAreaOfIsland(grid,sr-1,sc,area);_maxAreaOfIsland(grid,sr+1,sc,area);_maxAreaOfIsland(grid,sr,sc-1,area);_maxAreaOfIsland(grid,sr,sc+1,area);}int maxAreaOfIsland(vectorfor(int i = 0;i