一直进步 做喜欢的

深度优先搜索

深度优先搜索（Depth-First Search，DFS）是一种图遍历算法，它从起始顶点开始，依次访问其所有相邻顶点，并递归地对每个相邻顶点进行深度优先搜索，直到遍历完整个图。知识点：

• 栈：DFS可以使用栈来实现。从起始顶点开始，将其压入栈中，然后循环执行以下操作：从栈中取出一个顶点，并访问其所有未访问的相邻顶点，将其压入栈中。直到栈为空，搜索结束。
• 递归：DFS也可以使用递归实现。从起始顶点开始，依次递归地访问其所有相邻顶点，直到遍历完整个图。递归实现的优点是代码简洁清晰，但也有可能导致栈溢出。
• 标记数组：为了避免重复访问已经访问过的顶点，DFS通常使用一个布尔类型的标记数组来记录每个顶点是否已经访问过。
• 拓扑排序：DFS可以用来实现拓扑排序。拓扑排序是对有向无环图的所有顶点进行排序的一种算法。通过DFS，可以将图中的所有顶点按照其依赖关系排序，从而实现拓扑排序。
• 时间复杂度：DFS的时间复杂度取决于搜索过程中访问每个顶点的次数。对于稠密图，每个顶点都会被访问一次，因此时间复杂度为 O(V2)，其中 V 是顶点数。对于稀疏图，时间复杂度可以达到 O(V+E)，其中 E 是边数。
• 空间复杂度：DFS靠递归的堆栈记录⾛过的路径，要找到最短路径得把⼆叉树中所有树杈都探索完才能对⽐出最短的路径有多⻓，DFS 算法空间复杂度最坏情况下是树⾼度O(logN) 。
• 应用：DFS通常用于解决一些搜索深度较小的问题，例如拓扑排序、连通性判断等。由于DFS搜索深度较大时容易出现堆栈溢出等问题，因此需要选择合适的算法实现。

深度优先搜索——树专项

def traverse(root: Optional[TreeNode]):
    # root 需要做什么？在这做。
    # 其他的不⽤ root 操⼼，抛给框架
    traverse(root.left)
    traverse(root.right)

深度优先搜索——二叉搜索树专项

二叉搜索树的题本质都是中序遍历或者利用其性质任意节点的值要⼤于等于左⼦树所有节点的值且要⼩于等于右边⼦树的所有节点的值。

def BST(root: Optional[TreeNode], target):
    if root.val == target:
        # 到⽬标，做点什么
    if root.val < target:
        BST(root.right, target)
    if root.val > target:
        BST(root.left, target)

广度优先搜索BFS

广度优先搜索（Breadth-First Search，BFS）是一种图遍历算法，它从起始顶点开始，逐层访问其相邻顶点，并记录每个顶点到起始顶点的距离。知识点：

• 队列：BFS可以使用队列来实现。从起始顶点开始，将其放入队列中，然后循环执行以下操作：从队列中取出一个顶点，并访问其所有未访问的相邻顶点，将其放入队列中。直到队列为空，搜索结束。
• 标记数组：为了避免重复访问已经访问过的顶点，BFS通常使用一个布尔类型的标记数组来记录每个顶点是否已经访问过。同时，为了记录每个顶点到起始顶点的距离，可以使用一个整型数组来存储每个顶点的距离。
• 最短路径：BFS可以用来寻找无权图中起始顶点到其他顶点的最短路径。由于BFS是按层遍历的，因此可以保证从起始顶点到其他顶点的路径是最短的。
• 连通性：BFS可以用来判断图的连通性。如果从起始顶点开始可以访问到所有其他顶点，则图是连通的；否则，图是不连通的。
• 时间复杂度：BFS的时间复杂度取决于搜索过程中访问每个顶点的次数。对于稠密图，时间复杂度可以达到 O(V2)，其中 V 是顶点数。对于稀疏图，时间复杂度可以达到 O(V+E)，其中 E 是边数。
• 空间复杂度：BFS 借助队列做到⼀次⼀步⻬头并进，是可以在不遍历完整棵树的条件下找到最短距离。BFS 算法队列中每次都会储存着⼆叉树⼀层的节点，最坏情况下空间复杂度是树的最底层节点的数量O(N) 。
• 应用：BFS通常用于解决一些搜索深度较大的问题，例如最短路径、最小生成树等。由于BFS按层遍历，因此可以保证从起始顶点到其他顶点的路径是最短的。
• 变体：双向深度优先搜索（Bidirectional Depth-First Search，简称BDFS）可以在图或树中同时从起点和终点进行深度优先搜索，以期缩短搜索时间。
  • 原理：BDFS是双向搜索的一种变形，它通过同时从起点和终点进行深度优先搜索，以期在中间遇到一条路径，从而找到起点和终点之间的最短路径。在搜索过程中，需要记录起点和终点的已访问状态，直到两个搜索过程汇合，或者找到一条最短路径。
  • 特点：BDFS与DFS的搜索方式类似，只是在搜索过程中从起点和终点同时进行搜索。相比于BFS，BDFS的空间复杂度较低，但是对于图中较长路径，可能会超时或者陷入死循环。
  • 实现：BDFS的实现需要在搜索过程中记录起点和终点的已访问状态，并且需要判断是否有路径在中间汇合，或者找到一条最短路径。通常可以使用哈希表等数据结构来记录已访问状态，以及使用双向队列等数据结构来记录搜索过程中的路径。
  • 应用：BDFS可以用于寻找起点和终点之间的最短路径，例如在网络中找到两个节点之间的最短路径，或者在迷宫中找到从起点到终点的最短路径。另外，BDFS还可以用于图的遍历，例如在社交网络中寻找特定人群之间的联系，或者在语言处理中寻找两个词语之间的关系。

原地修改的问题可以不使用visited标记

from typing import List, Set, Tuple

class Node:
    def adj(self) -> List[Node]:
        pass

def BFS(start: Node, target: Node) -> int:
    q: List[Node] = []  # 核心数据结构
    visited: Set[Node] = set()  # 避免走回头路

q.append(start)  # 将起点加入队列
    # visited.add(start)
    step: int = 0  # 记录扩散的步数

while q:
        sz: int = len(q)
        # 将当前队列中的所有节点向四周扩散
        for i in range(sz):
            cur: Node = q.pop(0)
            # 划重点：这里判断是否到达终点
            if cur is target:
                return step
            # 将 cur 的相邻节点加入队列
            for x in cur.adj():
                if x not in visited:
                    q.append(x)
                    visited.add(x)
        # 划重点：更新步数在这里
        step += 1

回溯算法（Backtracking）是一种基于深度优先搜索的算法，它常用于在一组可能的解中搜索最优解。知识点：

• 原理：回溯算法是通过试错的方式进行搜索，即从一个可能的解开始搜索，如果发现当前解不可行，则回溯到上一步进行尝试。在搜索过程中需要记录当前已尝试的路径，并在每一步进行判断，如果当前路径已经不能满足要求，则需要进行回溯。
• 实现：回溯算法通常采用递归实现，每次搜索的参数包括当前路径、已访问状态等。在搜索过程中需要进行剪枝，即在当前路径已经不能满足要求时，提前结束搜索。在实现过程中需要注意，回溯算法通常可以通过状态重置来进行回溯，也可以通过栈等数据结构来记录搜索过程。
• 应用：回溯算法常用于求解组合、排列、子集等问题，例如在数独游戏中求解解，在密码破解中找到密码、图的遍历、求解最优化问题等。
• 优化：回溯算法的时间复杂度往往较高，常用的优化方法包括剪枝、记忆化搜索等。剪枝可以在搜索过程中排除不必要的搜索路径，从而减少搜索时间。记忆化搜索可以将已经搜索过的结果记录下来，避免重复搜索。另外，在实际应用中可以根据问题的特点进行算法的优化，例如在图的遍历中，可以使用启发式搜索等算法加速搜索过程。
• 时间复杂度：O(n!)，不像动态规划存在重叠⼦问题可以优化，回溯算法是纯暴⼒穷举。
• 技巧：回溯的撤销选择取决于是否对原始选择列表修改，如果修改则需要撤销操作。

回溯问题实际上是⼀个决策树的遍历过程。需要思考 3 个问题：

1. 路径：已经做出的选择
2. 选择列表：当前可以做的选择
3. 结束条件：到达决策树底层，⽆法再做选择的条件

排列题用used标记，组合题用start标记

result = []
def backtrack(path, choice_list):
    if target:
        result.add(path)
        return
    for choice in choice_list:
        # 做选择
        backtrack(path, choice_list)
        # 撤销选择