dfs序

### DFS序的概念 DFS序是指在深度优先搜索（Depth First Search, DFS）过程中访问节点的时间顺序记录。通常分为三种时间戳： 1. **进入时间**：首次访问某节点时的时间标记。 2. **退出时间**：完成对该节点及其子树的遍历并返回上一层时的时间标记。 3. **路径序列**：按照实际访问次序形成的节点序列。 这种序列化方式能够帮助我们快速判断某些关系，例如祖先-后代关系、子树范围等[^2]。 --- ### DFS序的实现 以下是基于图结构的DFS序实现方法： #### 方法一：递归实现 通过递归函数，在每次访问新节点时记录其进入时间和退出时间，并将其加入路径序列。 ```cpp #include <bits/stdc++.h> using namespace std; vector<vector<int>> adj; vector<int> enterTime, exitTime, pathOrder; int timer = 0; void dfs(int u) { enterTime[u] = ++timer; // 记录进入时间 pathOrder.push_back(u); // 将当前节点加入路径序列 for (auto &v : adj[u]) { if (!enterTime[v]) { // 如果未访问过 dfs(v); } } exitTime[u] = ++timer; // 记录退出时间 } // 主程序调用 int main() { int n, m; cin >> n >> m; adj.resize(n + 1), enterTime.assign(n + 1, 0), exitTime.assign(n + 1, 0); while (m--) { int a, b; cin >> a >> b; adj[a].push_back(b); } for (int i = 1; i <= n; ++i) { if (!enterTime[i]) { dfs(i); } } cout << "Path Order: "; for(auto node:pathOrder){ cout<<node<<" "; // 输出路径序列 } } ``` 上述代码实现了基本的DFS过程，并生成了路径序列 `pathOrder` 和对应的进入/退出时间数组 `enterTime`, `exitTime`[^3]。 --- #### 方法二：迭代实现 对于栈空间有限的情况，可以通过显式维护一个栈来模拟递归行为。 ```cpp stack<pair<int, bool>> stk; // pair<节点编号, 是否已处理子节点> stk.emplace(1, false); // 假设从节点1开始 while(!stk.empty()){ auto &[u, processed] = stk.top(); if(!processed){ enterTime[u] = ++timer; pathOrder.push_back(u); processed = true; // 标记为已处理 for(auto it=adj[u].rbegin();it!=adj[u].rend();++it){ // 反向压入子节点 if(!enterTime[*it]){ stk.emplace(*it, false); } } }else{ exitTime[u] = ++timer; stk.pop(); } } ``` 此版本避免了深递归可能导致的栈溢出问题。 --- ### DFS序的应用 1. **验证合法性**：给定一颗树以及部分缺失的DFS序，可通过重建完整的DFS序来检验输入是否合理。 2. **区间查询优化**：利用DFS序将树上的操作转化为线性表上的操作，从而加速动态规划或RMQ等问题求解速度。 3. **拓扑排序辅助工具**：虽然主要讨论的是BFS-based Kahn算法用于有向无环图(DAG)，但在特殊情况下也可以借助DFS得到逆后序作为最终结果之一[^1]。 ---