【算法与数据结构】——树的欧拉序和DFS序

ゝ一世哀愁。 2022-09-04 10:54 185阅读 0赞

### 文章目录 ###

*  本篇用到的输入和存图方法
 *  DFS序
 *  欧拉序
 *   *  欧拉序 1
     *  欧拉序 2

参考博客 [https://www.cnblogs.com/stelayuri/p/12702684.html][https_www.cnblogs.com_stelayuri_p_12702684.html]  
这篇文章写的很简洁，也很清楚，于是想记录下来。

**总结一下文中提到的几种搜索序列：我们将树通过DFS序转化为数组一般是为了更好的维护或者查找一个结点的子树信息**，因为DFS序中的第一次访问一个结点和第二次访问一个结点中间访问到的点是这个结点所有子树的结点。我们可以存两个数组,F1\[\],F2\[\]分别表示一个结点两次访问在DFS序的位置，这样在DFS序中tree\[F1\[i\],F2\[i\]\]这段序列就是所有i结点的子节点。  
我们常用的应该是本文中的欧拉序2。

# 本篇用到的输入和存图方法 #

输入方式：  
第一行两个数 n 和 root ，表示树共有 n 个节点，其中以编号为 root 的作为根节点  
接下来 n-1 行，每行两个整数 a b ，表示节点 a 与节点 b 相连

const int MAXN=1e4+50;
    
    int dfs_order[MAXN];
    int euler_order1[MAXN];
    int euler_order2[MAXN];
    
    bool vis[MAXN]; //访问标记
    vector<int> G[MAXN]; //邻接表存图
    int pos;
    
    int n,root,a,b;
    scanf("%d%d",&n,&root);
    for(int i=1;i<n;i++)
    { 
        scanf("%d%d",&a,&b);
        G[a].push_back(b);
        G[b].push_back(a);//双向存边
    }

# DFS序 #

顾名思义，DFS序就代表着树从根节点开始dfs的访问顺序  
也可以当作访问每个节点的时间戳  
![请添加图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NDg4NDUz_size_16_color_FFFFFF_t_70]  
以这棵树为例，根节点为 1  
按照从左到右的顺序搜索，则它的搜索顺序便是  
1 2 4 7 8 9 5 3 6  
在图中的顺序表示为  
![请添加图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NDg4NDUz_size_16_color_FFFFFF_t_70 1]  
DFS序的搜索代码：

void dfs(int p)
    { 
        dfs_order[++pos]=p; //访问到节点p时，++pos作为访问到的时间
        vis[p]=true;//标记访问
        for(int i:G[p])//再搜索未访问过的与p相邻的节点
            if(!vis[i])
                dfs(i);
    }

# 欧拉序 #

欧拉序长得跟dfs序相差无几  
储存的则是从根节点开始，按照dfs的顺序经过所有点再绕回原点的路径  
共存在两种欧拉序

## 欧拉序 1 ##

这一种欧拉序相当于是在dfs的时候，如果储存节点的栈变化一次，就把栈顶的节点编号记录下来,也就是说，每当访问完一个节点的子树，则需要返回一次该节点，再继续搜索该节点的其余子树,在树上的移动过程为  
![请添加图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NDg4NDUz_size_16_color_FFFFFF_t_70 2]  
它的搜索顺序便是  
1 2 4 7 4 8 4 9 4 2 5 2 1 3 6 3 1  
搜索代码：

void euler_dfs1(int p)
    { 
        euler_order1[++pos]=p;
        vis[p]=true;
        for(int i:G[p])
            if(!vis[i])
            { 
                euler_dfs1(i);
                euler_order1[++pos]=p; //与dfs序的差别，在搜索完一棵子树后就折返一次自己
            }
    } //数组需要开2倍n大

## 欧拉序 2 ##

这一种欧拉序相当于是在dfs的时候，如果某个节点入栈，就把这个节点记录下来，直到后面的操作中这个节点出栈，再记录一次这个节点  
也就是说，每个节点严格会在记录中出现两次，第一次是搜索到它的时候，第二次是它的子树完全被搜索完的时候  
除根节点外，每个节点严格两个入度两个出度  
在树上的移动过程为  
![请添加图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NDg4NDUz_size_16_color_FFFFFF_t_70 3]  
它的搜索顺序便是  
1 2 4 7 7 8 8 9 9 4 5 5 2 3 6 6 3 1  
可以发现，某个节点在顺序中出现的两次所围成的区间，就表示这个节点与它的子树  
欧拉序 2 的搜索代码：

void euler_dfs2(int p)
    { 
        euler_order2[++pos]=p;
        vis[p]=true;
        for(int i:G[p])
            if(!vis[i])
                euler_dfs2(i);
        euler_order2[++pos]=p; //与dfs序的差别，在所有子树搜索完后再折返自己
    } //数组需要开2倍n大

[https_www.cnblogs.com_stelayuri_p_12702684.html]: https://www.cnblogs.com/stelayuri/p/12702684.html
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NDg4NDUz_size_16_color_FFFFFF_t_70]: /images/20220829/c24f618f4e7b49b29b5c0b516680c833.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NDg4NDUz_size_16_color_FFFFFF_t_70 1]: /images/20220829/d2c4c5ce20eb43c6b021a880c3b7ac40.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NDg4NDUz_size_16_color_FFFFFF_t_70 2]: /images/20220829/f2c6c79e867b49518d039a9b5f0734fb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ1NDg4NDUz_size_16_color_FFFFFF_t_70 3]: /images/20220829/aacad484359c477aa6ff89137224ec74.png