DFS 序
一、 DFS 序
1. 定义
对树进行深度优先搜索遍历时，对于每个节点，在刚进入递归后及即将回溯前各记录一次该点的编号，得到的最后产生的长度为
2
N
2N
2N 的节点序列为 DFS 序；
void dfs(int i) {
d[++len] = i;
flag[i] = true;
for (int t = 0; t < g[i].size(); t++) {
int v = g[i][t];
if (!flag[v]) {
dfs(v);
}
}
d[++len] = i;
return;
}
2. 特点
每个节点
x
x
x 的编号在序列恰好存在两次； 设两次出现区间为
l
i
l_i
li 与
r
i
r_i
ri ，则闭区间
[
l
i
,
r
i
]
[l_i, r_i]
[li,ri] 就是以
x
x
x 为根的子树的 DFS 序；
则可以通过 DFS 序将子树的统计转化为序列上的区间统计；
3. 性质
树上任意两点
x
,
y
x, y
x,y 路径上的点为，最后一个
x
x
x 到第一个
y
y
y 之间出现奇数次的数，再加上两点的 LCA；
说明
由于在 DFS 序中节点
x
x
x 第一次出现的位置到最后一次出现的位置之间都是
x
x
x 子树上的节点；
所以在
x
x
x 节点最后一次出现到
y
y
y 节点第一次出现间的节点即为
x
x
x 与
y
y
y 的祖先；
但是，由于在这其中可能会遍历到其他不在两点路径上的子树，则这些字数上的节点均应是已经回溯的，则出现次数为 2 次，所以找这段区间中出现次数为奇数的节点，为两点上的路径；
由于在 DFS 序中，两点的遍历顺序为
x
→
L
C
A
(
x
,
y
)
→
y
x \rarr LCA(x, y) \rarr y
x→LCA(x,y)→y ，但是又由于 DFS 遍历时，只有进入节点与完全遍历完子树时才会记录，所以还要加上两点的 LCA；
4. DFN 序
DFN 序则为，在 DFN 序中该节点被搜索的次序 (时间戳) ；
void dfs(int i) {
dfn[i] = ++len;
flag[i] = true;
for (int t = 0; t < g[i].size(); t++) {
int v = g[i][t];
if (!flag[v]) {
dfs(v);
}
}
return;
}
二、欧拉序
1. 定义
进入节点时记录，每次遍历完一个子节点时，返回到此节点记录，得到的
2
∗
N
−
1
2 * N - 1
2∗N−1 长的序列；
void dfs(int i) {
d[++len] = i;
flag[i] = true;
for (int t = 0; t < g[i].size(); t++) {
int v = g[i][t];
if (!flag[v]) {
dfs(v);
d[++len] = i;
}
}
return;
}
2. 性质
节点
x
x
x 第一次出现与最后一次出现的位置之间的节点均为
x
x
x 的子节点； 任意两个节点的 LCA 。是欧拉序中两节点第一次出现位置中深度最小的节点； 说明 因为在欧拉序中节点
x
x
x 第一次出现的位置到最后一次出现的位置之间都是
x
x
x 子树上的节点； 所以在
x
x
x 节点最后一次出现到
y
y
y 节点第一次出现间的节点即为
x
x
x 与
y
y
y 的祖先； 但因为
x
x
x 可能为
y
y
y 的祖先，或
y
y
y 可能为
x
x
x 的祖先； 所以应查找
x
x
x 与
y
y
y 第一次出现的区间内的节点； 则可将
x
x
x 与
y
y
y 看作以其 LCA 为根的子树上的两个节点，则在欧拉序遍历时，顺序为
x
→
L
C
A
(
x
,
y
)
→
y
x \rarr LCA(x, y) \rarr y
x→LCA(x,y)→y ，则区间中深度最小的节点即为两点的 LCA ； 用 RMQ 计算
x
x
x 与
y
y
y 第一次出现的区间内深度最小的节点即可；
好文阅读
发表评论