图论——浅谈理论，DFS序、时间戳和欧拉序
提示：本文在树论基础上。
下文图例
DFS 序：1 2 4 5 7 9 8 3 6.
欧拉序：1 2 4 4 5 7 9 9 7 8 8 5 2 3 6 6 3 1.
回加欧拉序：1 2 4 2 5 7 9 7 5 8 5 2 1 2 3 6 3 1.
下文举例均指此图。
DFS 序
周所周知，DFS 为深度优先遍历，其框架如：
void dfs(int u, int fa) {
for (int v : g[u])
if (v != fa) dfs(v, u);
}
而 DFS 序就表示，DFS 遍历节点的顺序。
比如第 3 个遍历到的节点为 Q，则 DFS 序的第三个就是 Q。
其框架表示为：
void dfs1(int u, int fa) {
em.push_back(u);
for (int v : g[u])
if (v != fa) dfs(v, u);
}
举例：上图的 DFS 序即为：1 2 4 5 7 9 8 3 6.
DFN 序
一般认为 DFN 序与 DFS 序等价，或者 DFN 序是 DFS 序的逆。
这里采取第二种看法。
也就是 DFS 序的第 \(i\) 项（序列的第 \(i\) 个元素）的 DFN 为 \(i\)。
也就是，DFS 序是遍历的顺序，一个序列，记录第 \(x\) 个访问的是什么。
而 DFN 序则是记录第 \(i\) 个元素什么时候（\(x\)）访问的。
欧拉序 (2)
为什么后面有个 (2)？看下一个，有 (1) 你就知道了 .
通常认为的欧拉序为，记录每个节点入栈、出栈的顺序。
特性：叶子结点回被记录两次。
其框架表示为：
void dfs2(int u, int fa) {
em.push_back(u);
for (int v : g[u])
if (v != fa) dfs(v, u);
em.push_back(u);
}
举例：上图的 欧拉序 序即为：1 2 4 4 5 7 9 9 7 8 8 5 2 3 6 6 3 1.
(回加)欧拉序 (1)
有的地方也称为 欧拉序 (1) .
但是这个东西，似乎只有在 st 表求 LCA 的时候能用上（）
当然本人水平不够，具体情况具体分析（）
回加是我给加的形容词，之所以叫回加，是因为在 DFS 的过程中，当回到一个节点，也记录一次。
特性：叶子结点遍历完直接回到父亲节点，不重复记录。
同时，因为这个特性，当一个节点出栈的时候，不记录，因此叶子节点不会像欧拉序那样出现两次。
void dfs3(int u, int fa) {
em.push_back(u);
for (int v : g[u]) {
if (v != fa) dfs(v, u);
em.push_back(u);
} }
举例：上图的 回加欧拉序 序即为：1 2 4 2 5 7 9 7 5 8 5 2 1 2 3 6 3 1.
附：DFS 生成树
见：https://oi-wiki.org/graph/scc/#dfs-生成树
后期如果写 Tarjan 的时候再写。文章来源：https://www.toymoban.com/news/detail-805053.html
Reference
[1] https://www.cnblogs.com/stxy-ferryman/p/7741970.html
[2] https://zhuanlan.zhihu.com/p/467156796文章来源地址https://www.toymoban.com/news/detail-805053.html
到了这里，关于图论——浅谈理论，DFS序和欧拉序的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
