深度优先广度优先（深度优先广度优先动态规划）

## 深度优先搜索与广度优先搜索### 简介深度优先搜索 (Depth-First Search, DFS) 和广度优先搜索 (Breadth-First Search, BFS) 是两种常用的图遍历算法，它们在计算机科学和人工智能领域有着广泛的应用。它们的区别在于遍历图的方式，并因此适用于不同的问题场景。### 1. 深度优先搜索 (DFS)#### 1.1 原理深度优先搜索从图中一个顶点开始，沿着一条路径一直向下遍历，直到无法继续遍历为止，然后回溯到上一个节点，继续探索其他路径。它就像在一个迷宫中，一直沿着一条路走到底，如果走不通就返回，选择另一条路继续探索。#### 1.2 算法步骤1. 访问当前顶点并将其标记为已访问。 2. 从当前顶点的所有未访问邻接点中选择一个，将其标记为已访问并加入访问队列。 3. 递归地调用 DFS 函数，以该新顶点作为起始点。 4. 完成所有邻接顶点的遍历后，返回上一个顶点，继续探索其他路径。#### 1.3 应用场景

寻找图中的所有顶点，包括连通分量

判定图是否为连通图

寻找图中从一个顶点到另一个顶点的路径

拓扑排序#### 1.4 示例假设我们要在一个图中寻找从顶点 A 到顶点 E 的路径。```A/ \B C/ \ /D E ```DFS 算法会按照以下顺序访问顶点：A -> B -> D -> E。### 2. 广度优先搜索 (BFS)#### 2.1 原理广度优先搜索从图中一个顶点开始，先访问所有与该顶点直接相连的顶点，然后依次访问这些顶点的邻居，直到访问到所有可以到达的顶点。它就像一层一层地遍历图，先访问所有离起始点最近的顶点，然后是更远的顶点。#### 2.2 算法步骤1. 访问当前顶点并将其标记为已访问。 2. 将当前顶点加入一个队列。 3. 从队列中取出第一个顶点，访问其所有未访问的邻接顶点，将其标记为已访问并加入队列。 4. 重复步骤 3，直到队列为空。#### 2.3 应用场景

寻找图中从一个顶点到另一个顶点的最短路径

判定图是否为二分图

寻找图中所有连通分量

解决八数码难题#### 2.4 示例假设我们要在一个图中寻找从顶点 A 到顶点 E 的最短路径。```A/ \B C/ \ /D E ```BFS 算法会按照以下顺序访问顶点：A -> B -> C -> D -> E。### 3. 总结深度优先搜索和广度优先搜索都是图遍历算法，它们各自有不同的特点和应用场景：

DFS

: 擅长寻找路径，适合解决递归问题，时间复杂度为 O(V+E)，空间复杂度为 O(V)。

BFS

: 擅长寻找最短路径，适合解决层级问题，时间复杂度为 O(V+E)，空间复杂度为 O(V)。选择哪种算法取决于具体的问题需求。如果需要寻找路径，可以选择 DFS；如果需要寻找最短路径，可以选择 BFS。

深度优先搜索与广度优先搜索

简介深度优先搜索 (Depth-First Search, DFS) 和广度优先搜索 (Breadth-First Search, BFS) 是两种常用的图遍历算法，它们在计算机科学和人工智能领域有着广泛的应用。它们的区别在于遍历图的方式，并因此适用于不同的问题场景。

1. 深度优先搜索 (DFS)

1.1 原理深度优先搜索从图中一个顶点开始，沿着一条路径一直向下遍历，直到无法继续遍历为止，然后回溯到上一个节点，继续探索其他路径。它就像在一个迷宫中，一直沿着一条路走到底，如果走不通就返回，选择另一条路继续探索。

1.2 算法步骤1. 访问当前顶点并将其标记为已访问。 2. 从当前顶点的所有未访问邻接点中选择一个，将其标记为已访问并加入访问队列。 3. 递归地调用 DFS 函数，以该新顶点作为起始点。 4. 完成所有邻接顶点的遍历后，返回上一个顶点，继续探索其他路径。

1.3 应用场景* 寻找图中的所有顶点，包括连通分量 * 判定图是否为连通图 * 寻找图中从一个顶点到另一个顶点的路径 * 拓扑排序

1.4 示例假设我们要在一个图中寻找从顶点 A 到顶点 E 的路径。```A/ \B C/ \ /D E ```DFS 算法会按照以下顺序访问顶点：A -> B -> D -> E。

2. 广度优先搜索 (BFS)

2.1 原理广度优先搜索从图中一个顶点开始，先访问所有与该顶点直接相连的顶点，然后依次访问这些顶点的邻居，直到访问到所有可以到达的顶点。它就像一层一层地遍历图，先访问所有离起始点最近的顶点，然后是更远的顶点。

2.2 算法步骤1. 访问当前顶点并将其标记为已访问。 2. 将当前顶点加入一个队列。 3. 从队列中取出第一个顶点，访问其所有未访问的邻接顶点，将其标记为已访问并加入队列。 4. 重复步骤 3，直到队列为空。

2.3 应用场景* 寻找图中从一个顶点到另一个顶点的最短路径 * 判定图是否为二分图 * 寻找图中所有连通分量 * 解决八数码难题

2.4 示例假设我们要在一个图中寻找从顶点 A 到顶点 E 的最短路径。```A/ \B C/ \ /D E ```BFS 算法会按照以下顺序访问顶点：A -> B -> C -> D -> E。

3. 总结深度优先搜索和广度优先搜索都是图遍历算法，它们各自有不同的特点和应用场景：* **DFS**: 擅长寻找路径，适合解决递归问题，时间复杂度为 O(V+E)，空间复杂度为 O(V)。 * **BFS**: 擅长寻找最短路径，适合解决层级问题，时间复杂度为 O(V+E)，空间复杂度为 O(V)。选择哪种算法取决于具体的问题需求。如果需要寻找路径，可以选择 DFS；如果需要寻找最短路径，可以选择 BFS。