深度优先搜索——Python

算法原理

深度优先搜索是一种图的遍历算法，遍历每个节点一次，一般叫做DFS（Depth First Search）。

算法步骤如下：

1.访问节点v
2.再访问节点v的下一个未被访问的邻接点，并且置为当前节点，继续重复第1、2步骤；如果v的所有邻接点均访问过，则退回前一个含有未被访问过的邻接点的节点，重复第1、2步骤，直到所有节点都已访问过

大致思想是这样，用到的数据结构是栈，把访问过的节点压入栈中，并且标记节点已被访问，再遍历栈顶的未访问的邻接点，如果栈顶的邻接点都被访问过，就弹出栈，直到栈空，则遍历了一个联通的图。下面是用树结构画的动图来展现深搜的思想。

Python实现深搜算法

DFS实现有两种方式，一种是利用栈的数据结构，直接循环实现（非递归）；另一种是使用递归。

以二叉树的中序遍历为例，分别用两种方法实现。

递归方式容易理解，比较好实现：

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        ans = []  # 存储遍历结果
        def dfs(node):  # 中序遍历以node为根节点的树
            if not node:  # node节点为空则结束
                return
            dfs(node.left)
            ans.append(node.val)
            dfs(node.right)
        dfs(root)
        return ans

中序遍历的函数dfs，只要node节点非空，则递归遍历其左子树，然后访问根节点，最后递归遍历右子树。

非递归方式：

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        ans = []  # 存储遍历结果
        stk = []  # 栈，用于存储遍历的路径
        node = root  # 遍历的根节点
        while stk or node:  # 只要stk非空或node节点非空则说明还没遍历完
            while node:  # node节点非空
                stk.append(node)  # 则把node节点入栈，
                node = node.left  # 并且继续遍历其左子树
            node = stk.pop()  # node为空则说明遍历完了左子树，要返回上一个父节点，从stk弹出节点
            ans.append(node.val)  # 访问根节点
            node = node.right  # 接着遍历右子树
        return ans

在树的深搜当中，递归方式容易理解容易实现，但效率没有循环好。栈迭代虽然提高了效率，但里面嵌套了一层循环，不容易理解，所以结合一些其他人的实现方式和栈的特点，有另一种写法：

class Solution:
    def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:
        ans = []  # 存储遍历结果
        stk = [root]  # 栈，用于存储遍历的路径
        while stk:  # 栈非空
            node = stk.pop()  # 弹出一个节点
            if node is None:
                continue
            if isinstance(node, TreeNode):  # 如果node是一个树的节点
                stk.extend([node.right, node.val, node.left])  # 中序遍历的顺序是（左根右），压入栈中，则访问顺序就要反过来，根节点是值，而不是树节点
            else:
                ans.append(node)  # 访问根节点
        return ans

这种写法理解后是很好写的，而且效率相对来说更高。对于前序、后序遍历也都可以类似的实现，只需改一下节点访问的顺序。

应用

很多地方都能使用DFS深搜解决问题，下面是一些例子，可以去尝试做一做。

有的时候用深搜也容易超时，这个时候要考虑下优化，比如记忆化深搜，就是把一些计算的结果保存下来，下次还会用到时就可以直接调用，节省时间。

class Solution:
    def longestIncreasingPath(self, matrix: List[List[int]]) -> int:
        if not matrix:
            return 0
        m, n = len(matrix), len(matrix[0])  # 矩阵数组的行列形状
        max_len = 1  # 记录最大长度
        dfs_dict = {}  # 没有使用LRU缓存装饰器时，可以用一个字典来保存函数的结果
        # @lru_cache(None)  # LRU缓存机制，目的是记忆之前已经调用过的函数结果，再次使用时可以直接使用
        def dfs(i, j):  # 在位置i,j进行深搜，返回这个位置的最长长度
            L = 1  # 本身的长度为1
            dirs = [(-1, 0), (1, 0), (0, -1), (0, 1)]  # 四个方向
            for dx, dy in dirs:
                ii, jj = i + dx, j + dy  # 新的坐标
                if 0 <= ii < m and 0 <= jj < n and matrix[ii][jj] > matrix[i][j]:  # 新的坐标ii,jj合法并且值大于当前i,j
                    if (ii, jj) not in dfs_dict:
                        dfs_dict[(ii, jj)] = dfs(ii, jj) + 1  # 判断ii,jj的最长长度是否已经在记忆字典中
                    L = max(L, dfs_dict[(ii, jj)])  # 去最长的长度
            return L
        for i in range(m):
            for j in range(n):
                l = dfs(i, j)  # 循环每个位置的最长长度
                if l > max_len:
                    max_len = l
        return max_len