深度优先搜索

概念

深度优先搜索和广度优先搜索一样，都是对图进行搜索的算法，目的也都是从起点开始搜索直到到达指定顶点（终点）。深度优先搜索会沿着一条路径不断往下搜索直到不能再继续为止，然后再折返，开始搜索下一条候补路径。

具体而言

步骤1

A为起点，G为终点。一开始我们在起点A上。

步骤2

将可以从A直达的三个顶点B、C、D设为下一步的候补顶点。

步骤3

从候补顶点中选出一个顶点。优先选择最新成为候补的点，如果几个顶点同时成为候补，那么可以从中随意选择一个。

步骤4

此处B、C、D同时成为候补，所以我们随机选择了最左边的顶点。

步骤5

移动到选中的顶点B。此时我们在B上，所以B变为红色，同时将已经搜索过的顶点变为橙色。

步骤6

将可以从B直达的两个顶点E和F设为候补顶点。

步骤7

此时，最新成为候补顶点的是E和F，我们选择了左边的顶点E。

步骤8

移动到选中的顶点E上。

步骤9

将可以从E直达的顶点K设为候补顶点。

步骤10

重复上述操作直到到达终点，或者所有顶点都被遍历为止。

步骤11

这个示例的搜索顺序为A、B、E、K、F、C、H。

步骤12

现在我们搜索到了顶点C。

步骤13

到达终点G，搜索结束。

广度优先搜索与深度优先搜索的区别

广度优先搜索选择的是最早成为候补的顶点，因为顶点离起点越近就越早成为候补，所以会从离起点近的地方开始按顺序搜索；而深度优先搜索选择的则是最新成为候补的顶点，所以会一路往下，沿着新发现的路径不断深入搜索。

代码

题目

剑指offer55_二叉树的深度
题目描述：
输入一棵二叉树的根节点，求该树的深度。从根节点到叶节点依次经过的节点（含根、叶节点）形成树的一条路径，最长路径的长度为树的深度。
例如：

给定二叉树 [3,9,20,null,null,15,7]，

返回它的最大深度 3 。

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None
# 深度优先搜索
class Solution:
    def maxDepth(self, root):
        if root is None: 
            return 0 
        else: 
            left_height = self.maxDepth(root.left) 
            right_height = self.maxDepth(root.right) 
            return max(left_height, right_height) + 1 

资源下载地址：https://download.csdn.net/download/sheziqiong/85683069
资源下载地址：https://download.csdn.net/download/sheziqiong/85683069

1 深度优先遍历搜索(DFS)

• 1.1 算法介绍
• 1.2 实验结果

1.1 算法介绍

深度优先搜索算法（Depth-First-Search，DFS）是一种用于遍历或搜索树或图的算法。沿着树的深度遍历树的节点，尽可能深的搜索树的分支。当节点 v 的所在边都己被探寻过，搜索将回溯到发现节点 v 的那条边的起始节点。这一过程一直进行到已发现从源节点可达的所有节点为止。如果还存在未被发现的节点，则选择其中一个作为源节点并重复以上过程，整个进程反复进行直到所有节点都被访问为止。属于盲目搜索。

以上图为例，简述 DFS 的过程。首先从根节点“1”出发，按一定的顺序遍历其子节点，这里我们假设优先遍历左边的。所以，在遍历“1”之后，我们到了节点“2”，此时“2”仍有子节点，所以应继续向下遍历，下一个节点是“3”，然后是“4”。到了“4”之后，没有子节点了，说明我们已经将这一条路遍历完了，接着我们应该回溯，应该回到“4”的父节点，也就是“3”。因为“3”还有一个子节点“5”没有遍历，所以下一个我们应该遍历的是“5”。遍历完“5”之后又发现一条路到头了，再次回溯依然回溯到其父节点“3”，此时“3”的所有子节点都已经遍历完了，因该接着回溯到“3”的父节点“2”，然后检查“2”是否有没有遍历完的子节点。按照这样的规则，完成所有节点的遍历。最终得到的遍历顺序是“1-2-3-4-5-6-7-8-9-10-11-12”

在介绍了 DFS 在遍历树的应用后，我们将其应用于八数码问题的解决。八数码问题也称为九宫问题。在 3×3 的棋盘，摆有八个棋子，每个棋子上标有 1 至 8 的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格，与空格相邻的棋子可以移到空格中。要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。所谓问题的一个状态就是棋子在棋盘上的一种摆法。棋子移动后，状态就会发生改变。解八数码问题实际上就是找出从初始状态到达目标状态所经过的一系列中间过渡状态。

上面说的 DFS 遍历的树是已经存在的，我们只需要按照规定的遍历方法就能完成遍历，而对于八数码问题，没有已经存在的路径供我们遍历，需要我们从初始状态向下延伸（也就是上下左右移动）才能构造出类似的树。

以上图为例。在使用 DFS 进行搜索时，每个状态都会按照一定的顺序进行上下左右移动（在上图中是下、左、右、上的顺序），一次移动后会产生一个新的状态，然后以新状态为起点继续按约定的顺序（例如先向下）移动。终止的条件是找到解或者达到深度界限。那么如果按照图中下、左、右、上的顺序搜索后的结果将会是最左边的一条路一直是优先向下移动，如果不能向下则依次会是左、右、上的一种。

1.2 实验结果

以下面这个八数码为例，用 DFS 进行搜索。

将找出的解从初始状态一步一步输出到解状态。

可以看出总共进行了 15 次遍历，在某一条路的第 4 层找到了解。

下面我们来看一看 DFS 的所有 15 次遍历，以此来更深入的理解 DFS 的原理。稍微对代码进行改动，使其输出遍历次数和当前层数。由于结果太长，为了方便展示，下面将以树的形式展示。

上面输出的解就是按照红色路线标注找到的，从遍历次数可以看出 DFS 是一条道走到黑的找法，因为设置的深度界限是 4，所以每一条路最多找到第 4 层。

资源下载地址：https://download.csdn.net/download/sheziqiong/85683069
资源下载地址：https://download.csdn.net/download/sheziqiong/85683069

基本思路：
深度优先遍历图的方法是，从图中某顶点v出发：
（1）访问顶点v；
（2）依次从v的未被访问的邻接点出发，对图进行深度优先遍历；直至图中和v有路径相通的顶点都被访问；
（3）若此时图中尚有顶点未被访问，则从一个未被访问的顶点出发，重新进行深度优先遍历，直到图中所有顶点均被访问过为止。

例1：图像渲染

输入: image = [[1,1,1],[1,1,0],[1,0,1]]，sr = 1, sc = 1, newColor = 2
输出: [[2,2,2],[2,2,0],[2,0,1]]
解析: 在图像的正中间，(坐标(sr,sc)=(1,1)),在路径上所有符合条件的像素点的颜色都被更改成2。
注意，右下角的像素没有更改为2，因为它不是在上下左右四个方向上与初始点相连的像素点。

class Solution:
    def floodFill(self, image: List[List[int]], sr: int, sc: int, newColor: int) -> List[List[int]]:
        oldColor = image[sr][sc]
        if oldColor == newColor:
            return image
        def dfs(image,i,j):
            if i < 0 or i > len(image)-1 or j < 0 or j > len(image[0])-1 or image[i][j] != oldColor:
                return
            image[i][j] = newColor
            dfs(image,i+1,j)
            dfs(image,i-1,j)
            dfs(image,i,j+1)
            dfs(image,i,j-1)
            return image
        return dfs(image,sr,sc)

例2：岛屿数量
给一个01矩阵，1代表是陆地，0代表海洋， 如果两个1相邻，那么这两个1属于同一个岛。我们只考虑上下左右为相邻。
岛屿: 相邻陆地可以组成一个岛屿（相邻:上下左右） 判断岛屿个数。
例如：
输入
[
[1,1,0,0,0],
[0,1,0,1,1],
[0,0,0,1,1],
[0,0,0,0,0],
[0,0,1,1,1]
]
对应的输出为3

class Solution:
    def maxNumOfIsland(self , grid: List[List[int]]) -> int:
        def dfs(grid,i,j):
            if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] == 0:
                return
            grid[i][j] = 0
            dfs(grid,i+1,j)
            dfs(grid,i-1,j)
            dfs(grid,i,j+1)
            dfs(grid,i,j-1)           
        island = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1:
                    island += 1
                    dfs(grid,i,j)
        return island

例3：岛屿最大面积

输入：grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,1,1,0,1,0,0,0,0,0,0,0,0],[0,1,0,0,1,1,0,0,1,0,1,0,0],[0,1,0,0,1,1,0,0,1,1,1,0,0],[0,0,0,0,0,0,0,0,0,0,1,0,0],[0,0,0,0,0,0,0,1,1,1,0,0,0],[0,0,0,0,0,0,0,1,1,0,0,0,0]]
输出：6
解释：答案不应该是 11 ，因为岛屿只能包含水平或垂直这四个方向上的 1 。

class Solution:
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        max_island = 0
        def dfs(grid,i,j,res):
            if i < 0 or i > len(grid)-1 or j < 0 or j > len(grid[0])-1 or grid[i][j] == 0:
                return res
            res += grid[i][j]
            grid[i][j] = 0
            res = dfs(grid,i+1,j,res)
            res = dfs(grid,i-1,j,res)
            res = dfs(grid,i,j+1,res)
            res = dfs(grid,i,j-1,res)
            return res
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == 1:
                    max_island = max(max_island,dfs(grid,i,j,0))
        return max_island