搜索

递归回溯

原理:采用递归的方式遍历所有可能的解空间，当发现当前路径不满足条件时，回溯到上一步，尝试其他路径。通过递归函数的参数来记录当前的状态，如已选的元素、当前的位置等。

应用:解决排列组合问题（如全排列、子集生成）、迷宫求解问题、数独求解问题等。

二进制枚举

原理:将问题中的状态用二进制数表示，每一位代表一个元素是否被选中或某种状态是否存在，然后枚举所有可能的二进制数（从 0 到 2^n-1，n 为元素个数），对应不同的状态组合，判断是否满足条件。

应用:处理状态压缩问题，如集合的子集问题、资源分配问题（每个资源是否被使用）等。

DFS

原理:从图的某个顶点出发，沿着一条路径尽可能深地搜索下去，直到无法继续，然后回溯到上一个顶点，搜索其他路径。通常使用递归或栈来实现。

应用:图的遍历（如查找图中的所有连通分量）、求解连通性问题、迷宫路径搜索、求解所有可能的解（如排列组合问题的另一种解法）等。

BFS

原理:从图的某个顶点出发，先访问其所有相邻顶点，再依次访问这些相邻顶点的相邻顶点，按照层的顺序进行搜索，通常使用队列来实现。

应用:图的遍历（如求最短路径问题，在无权图中，BFS 可以找到从起点到终点的最短路径）、寻找连通分量、解迷宫问题（求最短出口路径）等。