浅谈DFS序

今天我们来学习一下DFS序

解决问题

给定一棵n个节点的树,m次查询,每次查询需要求出某个节点深度为h的所有子节点。

算法内容

对于这个问题,小学生的做法是:对每个节点保存所有深度的子节点,内存不行!或者每次查询遍历一遍树,

时间又会爆炸。

这个时候就需要用DFS序来维护这个树

首先进行预处理,把树的所有节点按照深度保存起来,每个深度的所有节点用一个线性保存,每个深度的节点相对顺序要和前序遍历一致。

从树的根节点进行DFS,对于每个节点记录两个信息,一个是DFS进入节点的时间in[id],另一个是DFS离开节点的时间out[id]。

对于每次查询,求绩点v在深度h的所有子节点,只需将深度为h并且DFS进入时间在in[v]与out[v]之间的所有节点求出来就可以。

原理分析

Step 1:

如下图,可以看到,由于普通的树并不具有区间的性质,所以在考虑使用线段树作为解题思路时,需要对给给定的数据进行转化,首先对这棵树进行一次dfs遍历,记录dfs序下每个点访问起始时间与结束时间,记录起始时间是前序遍历,结束时间是后序遍历,同时对这课树进行重标号。

《浅谈DFS序》

Step 2:

如下图,DFS之后,树的每个节点具有了区间的性质

《浅谈DFS序》

那么此时,每个节点对应了一个区间,而且可以看到,每个节点对应的区间正好“管辖”了它子树所有节点的区间,那么对点或子树的操作就转化为了对区间的操作。

【PS: 如果对树的遍历看不懂的话,不妨待会对照代码一步一步调试,或者在纸上模拟过程~】

Step3:

这个时候,每次对节点进行更新或者查询,就是线段树和树状数组最基本的实现了…

啦啦啦 搞定了,明天再把树链剖分好好复习一遍吧,睡觉睡觉TAT

例题:

待补

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注