一、什么是DFS序：

DFS序是按照先序遍歷，先遍歷根節點然后依次遍歷左子樹，右子樹的過程，每次遇到新的節點就把新訪問節點加到序列中，代碼如下：

int DFSrk[100000]; int cnt=0; int dfs(int u,int fa) {DFSrk[cnt++]=u;for(int i=head[u];i;i=ege[i].next){if(ege[i].to!=fa)dfs(ege[i].to,u);} } //vector儲存 如下 int dfs(int u,int fa) {DFSrk[cnt++]=u;for(int i=0;i<ege[u];i++){if(ege[u][i]=fa)dfs(ege[u][i],u);} }

二、DFS序性質

我么會發現對于圖中的三棵子樹他們的DFS序連續：

A-B-C-D-E-F-G-H

B-C-D-E

F-G-H

也就是說在一棵子樹上的DFS序，他們一定是連續的，那么我們可以做樹上的差分，這里可以保留一下，稍后填坑。

?

一、什么是時間戳：

時間戳我們有兩個標記第一個是第一次訪問的時候記錄一下，然后是在最后一次訪問時再標記一下。?

二、時間戳的性質：

我們可以直接通過時間戳來判斷一個節點是否是另一個節點的子節點。

一、什么是歐拉序：

歐拉是每次訪問一個點到一個點，就要存一次，無論這個點之前訪問過沒有，就要遇見點就存。還有就是有的會認為葉節點也訪問了兩次則有如下歐拉序：A-B-C-C-B-D-E-E-D-B-A-F-G-G-F-A

主要用途是tarjan，用起來很舒服，比如求LCA，求LCA以上都可以使用其實。

?

總結

以上是生活随笔為你收集整理的图论——Tarjan 初步 DFS序+时间戳+欧拉序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。