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

C++DFS深度优先搜索全解

news 2026/5/7 5:13:02

C++ DFS深度优先搜索全解

深度优先搜索（Depth-First Search，DFS）是一种用于遍历或搜索树或图的算法。其核心思想是尽可能深地搜索树的分支，直到无法继续为止，然后回溯到上一个节点继续搜索。以下将详细讲解DFS在各类问题中的应用及优化方法。

DFS走迷宫

迷宫问题通常涉及从起点到终点的路径搜索。DFS通过递归或栈结构实现路径探索。

算法步骤：

定义迷宫矩阵，标记起点和终点。
从起点出发，依次尝试四个方向（上、下、左、右）。
若当前方向可走且未被访问，则标记为已访问并递归进入下一步。
若到达终点，记录路径；否则回溯并尝试其他方向。

代码示例：

#include <iostream> #include <vector> using namespace std; vector<vector<int>> maze = { {0, 1, 0, 0}, {0, 1, 1, 0}, {0, 0, 0, 0}, {0, 1, 1, 0} }; vector<vector<bool>> visited(4, vector<bool>(4, false)); bool dfs(int x, int y, int endX, int endY) { if (x == endX && y == endY) return true; if (x < 0 || x >= 4 || y < 0 || y >= 4 || maze[x][y] == 1 || visited[x][y]) return false; visited[x][y] = true; if (dfs(x + 1, y, endX, endY) || dfs(x - 1, y, endX, endY) || dfs(x, y + 1, endX, endY) || dfs(x, y - 1, endX, endY)) return true; visited[x][y] = false; return false; }

DFS解决八皇后问题

八皇后问题要求在8×8棋盘上放置8个皇后，使其互不攻击。DFS通过回溯尝试所有可能的放置方式。

算法步骤：

按行放置皇后，依次尝试每一列。
检查当前位置是否与已放置皇后冲突（同列、对角线）。
若冲突则跳过；否则递归放置下一行。
若所有行放置完成，记录解。

代码示例：

#include <vector> #include <iostream> using namespace std; vector<vector<string>> solutions; bool isValid(vector<string>& board, int row, int col) { for (int i = 0; i < row; ++i) if (board[i][col] == 'Q') return false; for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; --i, --j) if (board[i][j] == 'Q') return false; for (int i = row - 1, j = col + 1; i >= 0 && j < 8; --i, ++j) if (board[i][j] == 'Q') return false; return true; } void dfs(vector<string>& board, int row) { if (row == 8) { solutions.push_back(board); return; } for (int col = 0; col < 8; ++col) { if (isValid(board, row, col)) { board[row][col] = 'Q'; dfs(board, row + 1); board[row][col] = '.'; } } }

DFS图的遍历

DFS可用于遍历图中的所有节点，适用于无向图和有向图。

算法步骤：

从起始节点开始，标记为已访问。
递归访问所有未访问的相邻节点。
使用邻接表或邻接矩阵存储图结构。

代码示例：

#include <vector> #include <iostream> using namespace std; vector<vector<int>> graph = {{1, 2}, {0, 3}, {0, 3}, {1, 2}}; vector<bool> visited(4, false); void dfs(int node) { visited[node] = true; cout << node << " "; for (int neighbor : graph[node]) if (!visited[neighbor]) dfs(neighbor); }

DFS无效路径优化与剪枝

剪枝通过提前终止无效分支提升效率，常见于组合优化问题。

剪枝策略：

可行性剪枝：当前路径不满足约束条件时终止。
最优性剪枝：当前路径已劣于已知最优解时终止。

示例：数独求解

bool isValid(vector<vector<char>>& board, int row, int col, char c) { for (int i = 0; i < 9; ++i) { if (board[row][i] == c) return false; if (board[i][col] == c) return false; if (board[3 * (row / 3) + i / 3][3 * (col / 3) + i % 3] == c) return false; } return true; } bool solveSudoku(vector<vector<char>>& board) { for (int i = 0; i < 9; ++i) { for (int j = 0; j < 9; ++j) { if (board[i][j] == '.') { for (char c = '1'; c <= '9'; ++c) { if (isValid(board, i, j, c)) { board[i][j] = c; if (solveSudoku(board)) return true; board[i][j] = '.'; } } return false; } } } return true; }

DFS的回溯机制

回溯是DFS的核心特性，通过撤销选择尝试其他可能性。

关键点：

选择：尝试一个候选解。
约束：检查是否满足条件。
目标：确认是否完成解。
撤销：回溯到上一步。

示例：全排列问题

void backtrack(vector<int>& nums, vector<vector<int>>& res, vector<int>& path) { if (path.size() == nums.size()) { res.push_back(path); return; } for (int num : nums) { if (find(path.begin(), path.end(), num) != path.end()) continue; path.push_back(num); backtrack(nums, res, path); path.pop_back(); } }

DFS在社会中的普及

DFS不仅是算法竞赛的必备技能，还广泛应用于实际场景：

路径规划：GPS导航、机器人寻路。
游戏开发：迷宫生成、AI决策树。
网络爬虫：深度优先抓取网页链接。
社交网络分析：好友关系链的深度探索。

案例：社交网络好友推荐DFS可用于遍历用户的好友关系链，发现潜在好友或社区结构。例如，通过深度遍历用户A的好友列表，推荐其好友的好友中未直接关联的用户。

总结

DFS通过递归或栈实现深度遍历，适用于路径搜索、组合问题、图遍历等场景。结合剪枝和回溯可大幅提升效率，其思想在技术和社会领域均有深远影响。

以下是DFSC++风格的伪代码实现，采用递归和迭代两种常见写法，并附简要说明：

C++伪代码

递归实现

void DFS_recursive(int node, vector<bool>& visited, const vector<vector<int>>& graph) { visited[node] = true; for (int neighbor : graph[node]) { if (!visited[neighbor]) { DFS_recursive(neighbor, visited, graph); } } }

标记当前节点为已访问
遍历所有未访问的相邻节点递归调用

迭代实现（使用栈）

void DFS_iterative(int start, vector<bool>& visited, const vector<vector<int>>& graph) { stack<int> s; s.push(start); visited[start] = true; while (!s.empty()) { int node = s.top(); s.pop(); for (int neighbor : graph[node]) { if (!visited[neighbor]) { visited[neighbor] = true; s.push(neighbor); } } } }