我的搜索题记整理

根据给定的信息，我们可以从这段代码中提取出两个主要的IT知识点：广度优先搜索（Breadth-First Search, BFS）与深度优先搜索（Depth-First Search, DFS）。接下来，我们将详细介绍这两个算法及其在代码中的应用。 ### 广度优先搜索（BFS） #### 概念 广度优先搜索是一种用于遍历或搜索树或图的算法。它从根节点开始，并探索尽可能靠近根的所有节点，然后再移动到下一层节点。这种搜索策略是按照层次进行的，即先访问所有当前层的节点之后再进入下一层。 #### 应用场景 BFS 在许多领域都有广泛的应用，包括但不限于： - 短路径问题 - 搜索所有可能的状态空间 - 计算图中两个节点之间的最短距离 #### 代码分析 在给定的代码片段中，`bfs` 函数实现了BFS算法，用于解决从节点 `a` 到节点 `b` 的最短路径问题。具体实现细节如下： 1. **初始化**：创建一个队列 `q` 来存储待访问的节点，将起点 `a` 放入队列，并标记为已访问。 2. **循环**：当队列非空时，从队列中取出第一个节点 `cnt`，对于该节点的每一种可能状态（加步长、减步长），计算新节点的位置 `tall`。 3. **边界条件**：如果新位置超出范围或者已经被访问过，则跳过此次循环。 4. **更新状态**：如果新位置没有被访问过，则将其加入队列，并标记为已访问。同时记录到达该节点所需的步数。 5. **结束条件**：如果到达终点 `b`，则返回所需的步数；如果遍历完所有可能的节点仍未找到终点，则返回 `-1`。 ### 深度优先搜索（DFS） #### 概念 深度优先搜索也是一种用于遍历或搜索树或图的算法。它从根节点开始，并尽可能深地沿着每条分支搜索，直到达到叶子节点或无法继续前进为止，然后回溯到上一个节点并继续探索。 #### 应用场景 DFS 通常用于以下场景： - 拓扑排序 - 图的连通性问题 - 解决迷宫问题 - 寻找所有可能的解决方案 #### 代码分析 在给定的代码片段中，`dfs` 函数实现了DFS算法，用于解决骑士走法问题。具体实现细节如下： 1. **初始化**：定义一个结构体 `node` 来存储骑士的位置坐标。创建一个二维数组 `vis` 来记录哪些位置已经访问过。 2. **递归函数**：`dfs` 函数接受当前位置坐标作为参数。如果当前步数等于目标步数，则设置标志位 `flag` 表示找到了一条解。 3. **探索路径**：对于当前位置的每一个可能移动方向（共有8个方向），检查新位置是否合法且未被访问过。 4. **递归调用**：如果新位置满足条件，则标记为已访问，并递归调用 `dfs` 函数。在每次递归返回后，需要撤销标记，以便后续分支能够继续探索。 5. **输出结果**：如果找到解，则按照骑士的移动顺序输出每个位置的坐标。 ### 总结 通过以上分析可以看出，BFS 和 DFS 是两种重要的图遍历算法，在不同的应用场景下有着各自的优势。BFS 更适合于寻找最短路径问题，而 DFS 则更适合于探索所有可能的路径或者解决方案。在实际应用中，选择合适的算法对于提高程序效率至关重要。