下面讲序的时候用的图
括号里是应用的场景, 不一定只能应用于相应的场景, 但是我个人觉得遇到比较多, 而且比较合理
下面的例子用这个树
然后用这个图
欧拉序(树)
dfs序指的就是dfs过程中访问到的节点的顺序
每个节点访问和离开的时候都会记录一下
所以每个节点会在dfs序上出现2次
欧拉序:
1 2 4 2 5 2 1 3 1 (号节点)
欧拉序长度可证明是2n-1
算法
- LCA(lowest Common Ancestors)
两个节点的lca一定是他们第一次出现的位置中间节点中, 深度最小的点
dfs序(树)
只在进入的时候算一次
emmm, 说实在的, 这是我一直以来的概念, 很多博客把dfs序进入和离开各算一次, 我也不知道对不对
dfs序:
1号节点 2号节点 4号节点 5号节点 3号节点
dfn(树)
dfn 是 Depth-First Numbering
其实dfn也不称之为序
一般这个数组名字是为了求节点第一次访问的时间戳.
硬要说序也可以说序, 其实就是按dfs序访问的时候, 从1-n标记一下.
也可以理解为做了一个映射
这样一来, 一棵树就变成了一个连续的数组, 我们在上面做一些操作就很容易
timer从0开始, 每次++timer按dfs序标注即可
1号节点对应的dfn是1
2号节点对应的dfn是2
3号节点对应的dfn是5
4号节点对应的dfn是3
5号节点对应的dfn是4
可以注意到一个节点的子树都是连续的标号, dfn数组操作的时候就可以一次性操作一颗子树了
用处
检测回路, 连通性, 查询路径上的属性
逆后序(图) Reverse Postorder
一个序列 arr = []
指的是在DFS完成搜索一个节点的所有邻接节点后, 该节点被加入序列
换句话说, 根据的是一个节点完成搜索的时间点
所以可以得知, 一个节点肯定是晚于他的子节点被加入序列的
从节点1开始的话, 逆后序是1 2 3 6 5 4 （并不唯一, 因为跟邻接节点的dfs顺序也有关系)
用处
- 求强连通分量
kosaraju和tarjan中都有使用 - 拓扑排序
DAG(有向无环图)中, 逆后序提供了一种天然的拓扑排序
此外, 逆后序还用于数据流分析(编译器优化), 递归依赖问题解决等
后序(图)
顾名思义, 后序就是逆后序没有压入栈, 进入的是队列
4 5 6 3 2 1
总结
一些用处讲的比较泛
本质上是我自己认知也不是很足