dfs序小总结

[王皓宇 (小鸽子)]

感觉真的要把普及和提高的图论总结帖写完了

---

咳咳，开始正题

dfs序有2（或3）种

如图，红色数字即dfs到的顺序

所以这里面的dfs序就是 [1,2,4,5,6,7,3,8,9,10]

有没有什么规律呢？

这样子可以快速更新子树的值和查询子树的值了

更重要的是，这样子就可以用数据结构维护了

于是我们就学会dfs序（其一）啦

（想必建dfs序是极简单的，所以不说了）

---

dfs序（其二）

同上图

dfs序是 [1,2,4,4,5,6,6,7,7,5,2,3,8,9,9,10,10,8,3]

这时候就有细心的小鸽子要说了

你这不就是在走的时候有重复说了一遍吗

你别说，还真是

所以想必你这个也会了，对吧

那么他们的区别在哪呢（其实没区别，因为结束节点可以直接通过起点加子树大小推算，所以除了帮助理解似乎没有什么用）

那么究竟是什么呢……

如果来时记录一下，走时记录一下，那为什么不只要经过就记录呢

一样如图

dfs序为 [1,2,4,2,1,3,5,3,6,3,7,3,1]

这个就是欧拉欧拉序（

他有什么用呢？

我们发现两个相同的数字间是该节点的一个儿子的子树

根据这个，我们发现两个点之间深度最小的节点就是这两个点的LCA

然后就没了？