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

C DFS深度优先搜索全解深度优先搜索Depth-First SearchDFS是一种用于遍历或搜索树或图的算法。其核心思想是尽可能深地搜索树的分支直到无法继续为止然后回溯到上一个节点继续搜索。以下将详细讲解DFS在各类问题中的应用及优化方法。DFS走迷宫迷宫问题通常涉及从起点到终点的路径搜索。DFS通过递归或栈结构实现路径探索。算法步骤定义迷宫矩阵标记起点和终点。从起点出发依次尝试四个方向上、下、左、右。若当前方向可走且未被访问则标记为已访问并递归进入下一步。若到达终点记录路径否则回溯并尝试其他方向。代码示例#include iostream #include vector using namespace std; vectorvectorint maze { {0, 1, 0, 0}, {0, 1, 1, 0}, {0, 0, 0, 0}, {0, 1, 1, 0} }; vectorvectorbool visited(4, vectorbool(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; vectorvectorstring solutions; bool isValid(vectorstring 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(vectorstring 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; vectorvectorint graph {{1, 2}, {0, 3}, {0, 3}, {1, 2}}; vectorbool 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(vectorvectorchar 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(vectorvectorchar 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(vectorint nums, vectorvectorint res, vectorint 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, vectorbool visited, const vectorvectorint graph) { visited[node] true; for (int neighbor : graph[node]) { if (!visited[neighbor]) { DFS_recursive(neighbor, visited, graph); } } }标记当前节点为已访问遍历所有未访问的相邻节点递归调用迭代实现使用栈void DFS_iterative(int start, vectorbool visited, const vectorvectorint graph) { stackint 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); } } } }初始化栈并压入起始节点每次弹出栈顶节点处理将未访问的邻居压入栈并标记参数说明graph邻接表表示的图结构vectorvectorintvisited记录节点访问状态的布尔数组node/start当前处理的节点索引复杂度分析时间O(VE)V为顶点数E为边数空间递归实现受调用栈深度影响迭代实现显式使用栈结构实际使用时需根据图的具体表示法调整邻接节点的访问方式。对于大规模图迭代实现通常更安全以避免栈溢出。