dfs 序

发表于 分类于 ，

dfs 序是一种处理树的方法， 它可以把树上的操作变为序列操作 , 从而简化树上的操作

如何生成 dfs 序

tree

首先，设置一个全局变量 dfs_clock, 它的作用是记录访问某个结点的时间
然后对树进行 dfs, 每次访问到一个结点时 dfs_clock 都 + 1
然后根据 dfs 时访问的顺序将树的每一个结点的信息存储下来

比如上面那棵树的 dfs 序就是: 1,2,5,6,3,4,7,8,9

伪代码: 

1
2
3
4
5
6
7
8
9
10
11
int dfs_clock(0);    //时间戳
int in[Mx],out[Mx];    //最先和最后访问时间
int a[Mx];
void dfs_order(int p)
{
    a[++dfs_clock] = p;
    in[p] = dfs_clock;
    for(x=child of p)
        dfs_order(x);
    out[p] = dfs_clock;
}

作用

记录下最先和最后的访问时间其实是为了访问以某个结点为根的子树

原理就是在某个结点最先访问时间之后和最后访问时间之前， 它的子树已经遍历过了，又因为每个结点都只会访问一遍， 所以在 [in [p],out [p]) 之间的所有节点都是以 p 为根的子树上的结点

那么，我们可以用树状数组 / 线段树存储 dfs 序，这样就可以快速做树上差分了 (O (logn) 查询，O (logn) 修改) 例题