当前位置：首页 > java >正文

C++深度优先搜索（DFS）、广度优先搜索（BFS）与动态规划（DP）详解

java 2025/7/13 21:36:11

C++深度优先搜索（DFS）、广度优先搜索（BFS）与动态规划（DP）详解

一、引言

在计算机科学中，搜索算法和动态规划是解决各种问题的关键工具。深度优先搜索（DFS）、广度优先搜索（BFS）和动态规划（DP）是三种非常重要的算法，它们在图遍历、最短路径、组合问题、优化问题等众多领域发挥着重要作用。对于初学者来说，深入理解和掌握这些算法是提升编程能力、解决复杂问题的重要一步。本文将从DFS、BFS和DP的基本概念讲起，逐步深入到其实现方法、应用场景，并通过大量代码示例和详细解释，帮助初学者全面掌握这些算法。

二、深度优先搜索（DFS）

（一）定义

深度优先搜索（DFS）是一种用于遍历或搜索树或图的算法。它的核心思想是从一个起始节点开始，沿着当前路径尽可能深地搜索，直到无法再前进时才回溯。这种搜索方式类似于沿着一条路径一直走到底，直到遇到死胡同才返回并尝试其他路径。

（二）与广度优先搜索的区别

深度优先搜索（DFS）和广度优先搜索（BFS）是两种常见的图搜索算法，它们的主要区别在于搜索策略和实现方式。DFS采用递归或栈实现，沿着一条路径一直走到底，直到无法再前进时才回溯。而BFS则使用队列实现，按照层次顺序逐层扩展搜索范围。在应用场景上，DFS适合解决路径搜索、连通性等问题，而BFS则在寻找最短路径、层级关系等方面更具优势。

（三）算法特性

遍历顺序：沿着路径尽可能深地搜索。
数据结构：栈（递归实现）或显式栈。
空间复杂度：O(d)，其中d为最大深度。
时间复杂度：O(V+E)，其中V为顶点数，E为边数。

（四）代码实现

以下是一个简单的DFS代码示例，用于遍历一个无向图：

#include <iostream>
#include <vector>
using namespace std;void dfsTraversal(vector<vector<int>>& graph, int node, vector<int>& visited) {visited[node] = 1; // 标记当前节点为已访问cout << node << " "; // 输出当前节点// 遍历当前节点的所有邻居节点for (int neighbor : graph[node]) {if (!visited[neighbor]) { // 如果邻居节点未被访问dfsTraversal(graph, neighbor, visited); // 递归访问邻居节点}}
}int main() {vector<vector<int>> graph = {{1, 2}, // 节点0的邻居节点{0, 3, 4}, // 节点1的邻居节点{0, 5}, // 节点2的邻居节点{1}, // 节点3的邻居节点{1}, // 节点4的邻居节点{2} // 节点5的邻居节点};int n = graph.size(); // 图的节点数vector<int> visited(n, 0); // 初始化访问数组，0表示未访问cout << "DFS Traversal: ";for (int i = 0; i < n; i++) { // 遍历所有节点if (!visited[i]) { // 如果当前节点未被访问dfsTraversal(graph, i, visited); // 从当前节点开始DFS}}return 0;
}

（五）详细解释

初始化访问标记：
- 使用vector<int>来标记节点是否被访问过，避免重复访问。
递归访问：
- 从起始节点开始，递归访问其所有未访问的邻居节点。
多源DFS：
- 如果图中有多个连通分量，需要从每个未访问的节点开始进行DFS。

三、广度优先搜索（BFS）

（一）定义

广度优先搜索（BFS）是一种用于遍历或搜索图或树的算法。它的核心思想是从一个起始节点开始，逐层遍历节点，先访问离起始节点最近的节点，再逐步扩展到更远的节点。这种搜索方式类似于在平静的水面上投入一颗石子，水波会以石子落水处为中心，一层一层向外扩散。

（二）与深度优先搜索的区别

（三）算法特性

遍历顺序：层级递增，逐层扩展。
数据结构：队列（先进先出，FIFO），适合逐层遍历。
空间复杂度：O(w)，其中w为最大宽度。
时间复杂度：O(V+E)，其中V为顶点数，E为边数。

（四）代码实现

以下是一个简单的BFS代码示例，用于遍历一个无向图：

#include <iostream>
#include <vector>
#include <queue>
using namespace std;void bfsTraversal(vector<vector<int>>& graph) {int n = graph.size(); // 图的节点数vector<int> visited(n, 0); // 初始化访问数组，0表示未访问queue<int> q; // 队列用于存储待访问的节点for (int i = 0; i < n; i++) { // 遍历所有节点if (!visited[i]) { // 如果当前节点未被访问q.push(i); // 将当前节点加入队列visited[i] = 1; // 标记当前节点为已访问while (!q.empty()) { // 当队列不为空时循环int cur = q.front(); // 获取队列中的第一个节点q.pop(); // 将该节点从队列中移除cout << cur << " "; // 输出当前节点// 遍历当前节点的所有邻居节点for (int j = 0; j < graph[cur].size(); j++) {int next = graph[cur][j]; // 获取邻居节点if (!visited[next]) { // 如果邻居节点未被访问q.push(next); // 将邻居节点加入队列visited[next] = 1; // 标记邻居节点为已访问}}}}}
}int main() {vector<vector<int>> graph = {{1, 2}, // 节点0的邻居节点{0, 3, 4}, // 节点1的邻居节点{0, 5}, // 节点2的邻居节点{1}, // 节点3的邻居节点{1}, // 节点4的邻居节点{2} // 节点5的邻居节点};cout << "BFS Traversal: ";bfsTraversal(graph);return 0;
}

（五）详细解释

初始化队列和访问标记：
- 使用queue<int>来存储待访问的节点。
- 使用vector<int>来标记节点是否被访问过，避免重复访问。
队列操作：
- 将起始节点加入队列，并标记为已访问。
- 当队列不为空时，循环处理队列中的节点。
处理当前节点：
- 从队列中取出一个节点，处理该节点（例如输出节点编号）。
- 遍历该节点的所有邻居节点，将未访问的邻居节点加入队列，并标记为已访问。
多源BFS：
- 如果图中有多个连通分量，需要从每个未访问的节点开始进行BFS。

四、动态规划（DP）

（一）定义

动态规划（DP）是一种用于解决多阶段决策过程的最优化问题的算法。它的核心思想是将问题分解为多个子问题，并通过存储子问题的解来避免重复计算。动态规划通常用于求解具有重叠子问题和最优子结构特性的问题。

（二）与贪心算法的区别

动态规划和贪心算法都是用于求解最优化问题的算法，但它们的主要区别在于解决问题的策略。贪心算法在每一步选择中都采取当前状态下最优的选择，从而希望导致结果是全局最优的。而动态规划则通过存储子问题的解来避免重复计算，确保找到全局最优解。

（三）算法特性

最优子结构：问题的最优解包含其子问题的最优解。
重叠子问题：子问题的解会被多次使用。
数据结构：通常使用数组或表来存储子问题的解。
空间复杂度：O(n)，其中n为子问题的数量。
时间复杂度：O(n)，其中n为子问题的数量。

（四）代码实现

以下是一个简单的动态规划代码示例，用于求解斐波那契数列：

#include <iostream>
#include <vector>
using namespace std;vector<int> fibonacci(int n) {vector<int> dp(n + 1, 0); // 初始化动态规划表dp[0] = 0; // 基础情况dp[1] = 1; // 基础情况for (int i = 2; i <= n; i++) { // 填充动态规划表dp[i] = dp[i - 1] + dp[i - 2];}return dp; // 返回动态规划表
}int main() {int n = 10; // 求解斐波那契数列的前10项vector<int> fib = fibonacci(n);cout << "Fibonacci Sequence: ";for (int i = 0; i <= n; i++) {cout << fib[i] << " ";}cout << endl;return 0;
}

（五）详细解释

初始化动态规划表：
- 使用vector<int>来存储子问题的解，避免重复计算。
基础情况：
- 初始化动态规划表的基础情况，例如斐波那契数列的前两项。
状态转移方程：
- 根据问题的特性，定义状态转移方程，例如斐波那契数列的每一项等于前两项之和。
填充动态规划表：
- 从基础情况开始，逐步填充动态规划表，直到求解出最终结果。

五、综合应用

（一）迷宫问题

迷宫问题是搜索算法和动态规划的经典应用场景。以下是一个使用DFS、BFS和DP解决迷宫问题的示例代码：

1. 使用DFS解决迷宫问题

#include <iostream>
#include <vector>
using namespace std;const int MAXN = 100;
int maze[MAXN][MAXN]; // 迷宫
int n, m; // 迷宫的大小bool isValid(int x, int y) {return x >= 0 && x < n && y >= 0 && y < m && maze[x][y] == 0;
}void dfsMaze(int x, int y, vector<vector<bool>>& visited) {visited[x][y] = true; // 标记当前节点为已访问cout << "(" << x << ", " << y << ") "; // 输出当前节点// 遍历四个方向int dx[4] = {0, 1, 0, -1};int dy[4] = {1, 0, -1, 0};for (int i = 0; i < 4; i++) {int nx = x + dx[i];int ny = y + dy[i];if (isValid(nx, ny) && !visited[nx][ny]) { // 如果新位置有效且未被访问dfsMaze(nx, ny, visited); // 递归访问新位置}}
}int main() {n = 5; m = 5; // 迷宫的大小// 构造迷宫maze[0][0] = maze[0][1] = maze[0][2] = maze[0][3] = maze[0][4] = 0;maze[1][0] = maze[1][1] = maze[1][2] = maze[1][3] = maze[1][4] = 0;maze[2][0] = maze[2][1] = maze[2][2] = maze[2][3] = maze[2][4] = 0;maze[3][0] = maze[3][1] = maze[3][