我們經(jīng)常會遇到樹的問題，但樹是非線性的結(jié)構(gòu)，操作起來始終還是麻煩，如果我們能把樹改造成線性結(jié)構(gòu)，有什么方法？對，就是今天要講的DSF序；
dfs序呢，就是把一棵樹區(qū)間化，我們用dfs的方式將它區(qū)間化。
如圖：
dfs序就是：ABDDEEBCFHHFG
其實就是用dfs全部遍歷一遍，不過我們不能光遍歷還有動些小手腳，我們要在遍歷的同時記錄每個節(jié)點進(jìn)棧與出棧的時間序列。

介紹兩個基本函數(shù)：in[x],out[x]
dfs從根節(jié)點開始，這倆函數(shù)就分別記錄每個節(jié)點x進(jìn)入與離開的時間戳
還有num[x]，表示第x個節(jié)點的編號

inline int dfs(int x,int fa,int time) {in[x]=++time;num[time]=x;for(int i=1;i<=e[x].size();i++){int w=e[x][i];if(w==fa)continue;//防止又從子節(jié)點找回去dfs(w,x,time); }out[x]=time; } dfs(s,0,0);

（具體情況根據(jù)，根據(jù)題目來寫）
num生成的就是一個新秩序，由每個節(jié)點進(jìn)入關(guān)系而形成的
你仔細(xì)觀察會發(fā)現(xiàn)：
序根節(jié)點的進(jìn)棧時間<子樹的dfs<根節(jié)點的出棧時間
這樣不就成一個區(qū)間了
in[x]~out[x]是x為根節(jié)點的子樹，劃分為一個區(qū)間
然后什么單點修改，區(qū)間查詢，莫隊都可以用在樹上，而且dfs序也是樹鏈剖分的前驅(qū)知識

光說可能不怎么懂，我去找一些題，做完再更新例題

總結(jié)

以上是生活随笔為你收集整理的DFS序讲解的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。