DFS与组合c++

### C++ 实现 DFS 深度优先搜索与组合问题 以下是基于给定引用内容以及专业知识，提供关于如何用 C++ 实现深度优先搜索（DFS）及其在解决组合问题中的应用。 #### 使用递归实现 DFS 的基本框架 深度优先搜索可以通过递归来实现，这是一种非常直观的方法。以下是一个通用的递归模板： ```cpp void dfs(int node, vector<vector<int>>& graph, vector<bool>& visited) { visited[node] = true; // 访问当前节点并标记为已访问 cout << "Visited Node: " << node << endl; for (int neighbor : graph[node]) { // 遍历当前节点的所有邻居 if (!visited[neighbor]) { // 如果邻居未被访问，则继续深搜 dfs(neighbor, graph, visited); } } } ``` 此代码片段展示了如何通过递归方式访问图中的每一个节点[^1]。 #### 解决组合问题的具体实现 对于组合问题，例如 LeetCode 上的经典题目——给定两个整数 `n` 和 `k`，返回 `[1, n]` 范围内的所有可能的 `k` 个数的组合，可以利用 DFS 来枚举所有的解空间树。下面给出具体的解决方案： ```cpp #include <iostream> #include <vector> using namespace std; // 定义全局变量存储最终结果和临时路径 vector<vector<int>> result; vector<int> path; // 主函数用于调用dfs void combineDfs(int n, int k, int startIdx) { if (path.size() == k) { // 当前路径长度等于目标大小时加入结果集 result.push_back(path); return; } for (int i = startIdx; i <= n; ++i) { // 枚举从startIdx到n之间的每个数字 path.push_back(i); // 将当前数字加入路径 combineDfs(n, k, i + 1); // 进入下一层决策树 path.pop_back(); // 回溯操作，移除最后一个数字恢复状态 } } int main() { int n = 4, k = 2; // 输入参数定义 combineDfs(n, k, 1); // 开始回溯过程 for (const auto& vec : result) { // 输出所有符合条件的结果 for (int num : vec) { cout << num << ' '; } cout << '\n'; } return 0; } ``` 上述程序实现了使用 DFS 方法求解指定范围内所有满足条件的子集合的功能[^2]。 #### 利用 Stack 数据结构模拟非递归版本的 DFS 除了传统的递归方法外，还可以借助显式的栈数据结构来完成同样的功能。这种方法尤其适用于那些可能存在极深递归层次从而引发堆栈溢出风险的情况。下面是采用迭代形式而非递归形式的一个例子： ```cpp #include <iostream> #include <vector> #include <stack> using namespace std; vector<vector<int>> iterativeDfs(const vector<vector<int>>& adjList) { vector<vector<int>> res; stack<pair<int, bool>> stk; // pair.first表示顶点编号,pair.second标志是否第一次进入该结点 vector<bool> visited(adjList.size(), false); stk.emplace(make_pair(0, false)); // 初始化根节点压入栈中 while (!stk.empty()) { auto [node, expanded] = stk.top(); stk.pop(); if (!expanded && !visited[node]) { visited[node] = true; res.emplace_back(vector<int>{node}); stk.emplace(node, true); // 再次将本节点压入栈以便后续处理其邻接点 for(auto it=adjList[node].rbegin();it!=adjList[node].rend();++it){ if(!visited[*it]){ stk.emplace(*it,false); } } } else{ continue; } } return res; } ``` 这段代码展示了一个不依赖于隐式调用栈而是依靠显示管理的 LIFO 结构来进行遍历的过程[^3]。 ---