首页 > 其他分享 >DFS序和欧拉序的降维打击

DFS序和欧拉序的降维打击

时间：2023-11-24 13:32:39浏览次数：39  
标签：cur int 割点 DFS 降维 maxn low 节点 欧拉

1. DFS 序和时间戳

1.1 DFS 序

定义：树的每一个节点在深度优先遍历中进、出栈的时间序列。

如下树的 dfs 序就是[1,2,8,8,5,5,2,4,3,9,9,3,6,6,4,7,7,1]。

5.png

下图为生成DFS的过程。对于一棵树进行DFS序，除了进入当前节点时对此节点进行记录，同时在回溯到当前节点时对其也记录一下，所以DFS序中一个节点的信息会出现两次。

Tips： 因为在树上深度搜索时可以选择从任一节点开始，所以DFS序不是唯一的。

6.png

DFS序的特点：

  • 可以把树数据结构转换为线性数据结构，从而可以把基于线性数据的算法间接用于处理树上的问题。堪称降维打击。

  • 相同编号之间的节点编号为以此编号为根节点的子树上的所有节点编号。

    [2,8,8,5,5,2]表示编号 2为根节点的子树中所有节点为8,5。

    [4,3,9,9,3,6,6,4]表示编号 4为根节点的子树中所有节点为 3,9,6。

  • 如果一个节点的编号连续相同，则此节点为叶节点。

  • 树的DFS序的长度是2N（N表示节点的数量）。

2.png

求DFS序的代码：

#include <cstdio>
using namespace std;
const int maxn=1e5+10;
int n;
int tot,to[maxn<<1],nxt[maxn<<1],head[maxn];
int id[maxn],cnt;
void add(int x,int y)
{
    to[++tot]=y;
    nxt[tot]=head[x];
    head[x]=tot;
}
void dfs(int x,int f)
{
    id[++cnt]=x;
    for(int i=head[x];i;i=nxt[i])
    {
        int y=to[i];
        if(y==f)
            continue;
        dfs(y,x);
    }
    id[++cnt]=x;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<n;i++)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    dfs(1,0);
    for(int i=1;i<=cnt;i++)
        printf("%d ",id[i]);
    return 0;
}

测试数据：

9
1 2
1 4
1 7
2 8
2 5
4 3
4 6
3 9

1.2 时间戳

按照深度优先遍历的过程，按每个节点第一次被访问的顺序，依次给予这些节点1−N的标记，这个标记就是时间戳。如果一个点的起始时间和终结时间被另一个点包括，这个点肯定是另一个点的子节点（简称括号化定理）。每棵子树 x 在 DFS 序列中一定是连续的一段，结点 x 一定在这段的开头。

7.png

dfs与时间戳的关系，对应列表中索引号和值的关系。

8.png

在dfs代码中添加进入节点时的顺序和离开节点时的顺序。

//……
//in 开始时间 out 结束时间
int in[maxn],out[maxn];
//……
void dfs(int x,int f) {
	//节点的 dfs 序
	id[++cnt]=x;
	//开始时间
	in[x]=cnt;
	for(int i=head[x]; i; i=nxt[i]) {
		int y=to[i];
		if(y==f)
			continue;
		dfs(y,x);
	}
	id[++cnt]=x;
	//结束时间
	out[x]=cnt;
}
//……

3. DFS 序的应用

3.1 割点

什么是割点？

如果去掉一个节点以及与它连接的边，该点原来所在的图被分成两部分，则称该点为割点。如下图所示，删除 2号节点，剩下的节点之间就不能两两相互到达了。例如 4号不能到5号，6号也不能到达1号等等。一个连通分量变成两个连通分量！

9.png

怎么判断图是否存在割点以及如何找出图的割点？

Tarjan 算法是图论中非常实用且常用的算法之一，能解决强连通分量、双连通分量、割点和割边（桥）、求最近公共祖先（LCA）等问题。

Tarjan算法求解割点的核心理念：

  • 在深度优先遍历算法访问到k点时，此时图会被k点分割成已经被访问过的点和没有被访问过的点。
  • 如果k点是割点，则没有被访问过的点中至少会有一个点在不经过k点的情况下，是无论如何再也回不到已访问过的点了。则可证明k点是割点。

下图是深度优先遍历访问到2号顶点的时候。没有被访问到的顶点有4、5、6号顶点。

Tips： 节点边上的数字表示时间戳。

10.png

其中5和6号顶点都不可能在不经过2号顶点的情况下，再次回到已被访问过的顶点(1和3号顶点)，因此2号顶点是割点。

问题变成如何在深度搜索到 k点时判断，没有被访问过的点是否能通过此k或者不能通过此k点回到曾经访问过的点。

算法中引入了回溯值概念。

回溯值表示从当前节点能回访到时间戳最小的祖先，回溯值一般使用名为 low的数组存储，low[i]表示节点 i的回溯值。

如下演示如何初始化以及更新节点的 low值。

  • 定义3 个数组。vis[i]记录节点是否访问过、dfn[i]记录节点的时间戳、low[i]记录节点的回溯值。如下图所示，从 1号节点开始深搜，搜索到4号节点时，3个数组中的值的变化如下。也就是说，初始，节点的 low值和dfn值相同。或者说此时，回溯值还不能确定。

    Tips：注意一个细节，由1->3，认为 1是3的父节点。

11.png

  • 搜索到4号时，与4号相连的边有4->1，4->1是没有访问过的边，且1号节点已经标记过访问过，也就是说通过4号点又回到了1号点。所以说4->1是一条回边，或者说 1-……-4之间存在一个环。则4号点的 low[4]=min( low[4],dfn[1] )=1

12.png

  • 因为 2是4的父节点，显然也是能通过4号点回到1号点，所以也需要更新其low值，更新表达式为 low[2]=min(low[2],low[4])。同理3号点是2号点的父节点，也能通过 3->2->4->1回到1号点。所以3号点的low也需要更新。low[3]=min(low[2],low[3])。

13.png

  • 继续更新5、6号节点的low值。

14.png

根据这些信息，如何判断割点。

  • 如果当前点为根节点时，若子树数量大于一，则说明该点为割点（子树数量不等于与该点连接的边数）。
  • 如果当前点不为根节点，若存在一个儿子节点的low值大于或等于该点的dfn值时（low[子节点] >= dfn[父节点]），该点为割点（即子节点，无法通过回边，到达某一部分节点（这些节点的dfn值小于父亲节点））。这个道理是很好理解的，说明子节点想重回树的根节点是无法绕开父节点。

3.2 割边

定义：即在一个无向连通图中，如果删除某条边后，图不再连通。如下图删除2-5和5-6后，图不再具有连通性。 15.png

删除2-5和5-6边后。

16.png

那么如何求割边呢？

只需要将求割点的算法修改一个符号就可以。只需将low[v]>=num[u]改为low[v]>num[u]，取消一个等于号即可。因为low[v>=num[u]代表的是点v 是不可能在不经过父亲结点u而回到祖先（包括父亲）的，所以顶点u是割点。

如果low[y]和num[x]相等则表示还可以回到父亲，而low[v]>num[u]则表示连父亲都回不到了。倘若顶点v不能回到祖先，也没有另外一条路能回到父亲，那么 w-v这条边就是割边，

3.3 Tarjan 算法

#include <iostream>
#include <string.h>
#include <string>
#include <algorithm>
#include <math.h>
#include <vector>
using namespace std;
const int maxn = 123456;
int n, m, dfn[maxn], low[maxn], vis[maxn], ans, tim;

bool cut[maxn];
vector<int> edge[maxn];

void cut_bri(int cur, int pop) {
	vis[cur] = 1;// 1表示正在访问中
	dfn[cur] = low[cur] = ++tim;
	int children = 0; //子树数量
	for (int i : edge[cur]) { //对于每一条边
		if (i == pop || vis[cur] == 2)
			continue;
		if (vis[i] == 1) //遇到回边
			low[cur] = min(low[cur], dfn[i]); //回边处的更新 (有环)
		if (vis[i] == 0) {
			cut_bri(i, cur);
			children++;  //记录子树数目
			low[cur] = min(low[cur], low[i]); //父子节点处的回溯更新
			if ((pop == -1 && children > 1) || (pop != -1 && low[i] >= dfn[cur])) { //判断割点
				if (!cut[cur])
					ans++;   //记录割点个数
				cut[cur] = true; //处理割点
			}
			if(low[i]>dfn[cur]) { //判断割边
				edge[cur][i]=edge[i][cur]=true;  //low[i]>dfn[cur]即说明(i,cur)是桥(割边)；
			}
		}
	}
	vis[cur] = 2; //标记已访问
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		edge[x].push_back(y);
		edge[y].push_back(x);
	}
	for (int i = 1; i <= n; i++) {
		if (vis[i] == 0)
			cut_bri(i, -1); //防止原来的图并不是一个连通块
		//对于每个连通块调用一次cut_bri
	}
	printf("%d\n", ans);
	for (int i = 1; i <= n; i++) //输出割点
		if (cut[i])
			printf("%d ", i);
	return 0;
}

4.欧拉序

定义：进入节点时记录，每次遍历完一个子节点时，返回到此节点记录，得到的 2 ∗ N − 1 长的序列；

欧拉序和DFS序的区别，前者在每一个子节点访问后都要记录自己，后者只需要访问完所有子节点后再记录一次。如下图的欧拉序就是： 1 2 8 2 5 2 1 7 1 4 3 9 3 4 6 4 1。每个点在欧拉序中出现的次数等于这个点的度数，因为DFS到的时候加进一次，回去的时候也加进。

17.png

1.png

性质：

  • 节点 x 第一次出现与最后一次出现的位置之间的节点均为 x 的子节点；

  • 任意两个节点的 LCA 是欧拉序中两节点第一次出现位置中深度最小的节点。两个节点第一次出现的位置之间一定有它们的LCA，并且，这个LCA一定是这个区间中深度最小的点。

根据欧拉序的性质，可以用来求解CLA。如上图，求解 LCA(9,6)。

  • 在欧拉序中找到9和6第一次出现的位置。

18.png

  • 直观比较，知道4号节点是其LCA，特征是9和6之间深度最小的节点。

欧拉序求LCA，先求图的欧拉序、时间戳（可以记录进入和离开节点的时间）以及节点深度。有了这些信息，理论上足以求出任意两点的LCA。变成了典型的RMQ问题。

19.png

为了提升多次查询性能，可以使用ST表根据节点的深度缓存节点的信息。j=0时如下图所示。

20.png

j=1表示区间长度为 2，值为区间长度为 1的两个子区间的深度值小的节点。

21.png

欧拉序求LCA

#include <iostream>
#include <string.h>
#include <string>
#include <algorithm>
#include <math.h>
#include <vector>
using namespace std;
const int maxn = 10000;
int n, m, dfn[maxn], dep[maxn], tim;
int ol[maxn];
int st[maxn][maxn],lg2[maxn];
vector<int> edge[maxn];
void dfs(int cur, int fa) {
	ol[++tim]=cur;
	dfn[cur]=tim;
	dep[cur]=dep[fa]+1;
	for (int v : edge[cur]) { //对于每一条边
		if(v==fa)continue;
		dfs(v,cur);
		ol[++tim]=cur;
	}
}

void stPreprocess() {
	lg2[0] = -1;  // 预处理 lg 代替库函数 log2 来优化常数
	for (int i = 1; i <= (n << 1); ++i) {
		lg2[i] = lg2[i >> 1] + 1;
	}
	for (int i = 1; i <= (n << 1) - 1; ++i) {
		st[i][0] = ol[i];
	}
	for (int j = 1; j <= lg2[(n << 1) - 1]; ++j) {
		for (int i = 1; i + (1 << j) - 1 <= ((n << 1) - 1); ++i) {
			st[i][j] = dep[ st[i] [ j - 1 ] ] < dep[ st[ i + (1 << j - 1)][j - 1 ]    ]  ? st[i][j - 1 ] : st[ i + (1 << j - 1)][j - 1 ];
		}
		cout<<endl;
	}
}

int getlca(int u, int v) {
	if(dfn[u]>dfn[v])swap(u,v);
	u=dfn[u],v=dfn[v];
	int d=lg2[v-u+1];
	int f1=st[ u ][d  ];
	int f2=st[v-(1<<d)+1 ][ d ];
	return dep[f1]<dep[f2]?f1:f2;
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= m; i++) {
		int x, y;
		scanf("%d%d", &x, &y);
		edge[x].push_back(y);
		edge[y].push_back(x);
	}
	dfs(1, 0);
	for (int i = 1; i <= 2*n-1; i++) //输出割点
		printf("%d-%d  ", ol[i],dfn[ ol[i] ]);

	stPreprocess();
	int u,v;
	cin>>u>>v;
	int res=getlca(u,v);
	cout<< res;
	return 0;
}

5. 总结

DFS序和欧拉序并不难理解，正如四两拨千斤，却能解决很多复杂的问题。

标签：cur,int,割点,DFS,降维,maxn,low,节点,欧拉
From： https://blog.51cto.com/gkcode/8548537

相关文章

  • dfs-单词匹配2
    题目描述在一个字符矩阵中，可把横向或竖向连续相邻的字符、按顺序组成一个单词，例如下图所示的XE、ACX、STJIIE给定一个字符矩阵charMatrix和目标单词列表words，请计算这个字符矩阵可以组成多少个words中的单词，并返回这个数量：矩阵中每个格子的字符，对于同一个单词不能重复使......
  • dfs思想方式
    dfs深度优先搜索：一条路走到黑基本模型:Returntypedfs(参数){判断边界（返回）扩展状态dfs下一步返回}dfs+记忆返回值=记忆化搜索  classSolution{public:intminPathCost(vector<vector<int>>&grid,vector<vector<int>>&moveCost){......
  • acwing 第 130 场周赛  (前缀和，dfs，对不同边的处理)
      #include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include<climits>usingnamespacestd;typedeflonglongLL;constintN=5010;intn;inta[N];LLs[N];LLget(intl,intr){return......
  • loj144&145 dfs序+树状数组/线段树
    https://loj.ac/p/144https://loj.ac/p/145两题非常相似，一题的权值修改是在点上的，一题的权值修改是在整棵子树上的。首先我们要了解dfs序，并记录每个节点的子树大小sz，对于一个节点，在dfs序上sz长的区间全都是他的子节点以及他自己。所以我们将一棵树映射到了一个区间上，并且可......
  • Unity中欧拉角
    什么是欧拉角？（1）使用单个角度来保存方位（2）X与Z沿自身坐标系旋转，Y沿世界坐标旋转（3）API：Vector3eulerAngle=this.tranform.rulerAngles;优点：（1）仅使用三个数字表达方位，占用空间小（2）沿坐标轴旋转的单位维角度，符合人的思考方式（3）任意三个数字都是合法的，不存在不合法的欧拉角缺点:（1）方......
  • HDFS与MAPREDUCE操作
     HDFS文件操作在分布式文件系统上验证HDFS文件命令，如下。hadoopfs[genericOpitions][-ls<path>] //显示目标路径当前目录下的所有文件[-lsr<path>] //递归显示目标路径下的所有目录及文件（深度优先）[-du<path>] //以字节为单位显示目录中所有文件的大小，或该文......
  • centos7.9 部署FastDFS+Nginx本地搭建文件服务器 高性能的文件服务器集群 同时实现在
    前言FastDFS是一个开源的轻量级分布式文件系统，它对文件进行管理，功能包括：文件存储、文件同步、文件访问（文件上传、文件下载）等，解决了大容量存储和负载均衡的问题。特别适合以文件为载体的在线服务，如相册网站、视频网站等等。FastDFS为互联网量身定制，充分考虑了冗余备份、负载均衡、线......
  • DFS 序
      最近接触到一些DFS序的题，它可以用来解决一些关于子树的问题。  DFS序本质就是一棵树在深度优先搜索时访问节点的顺序。比如有下面一棵树，其DFS序就是$1\;2\;4\;7\;8\;5\;3\;6\;9$。  DFS序有一个很重要的性质，以节点$u$为根的子树中所有的节点......
  • 深度优先搜索（DFS）
    深度优先搜索（DFS）我们以二叉树的遍历为例子。先序遍历遍历过程访问根节点先序遍历其左子树先序遍历其右子树中序序遍历遍历过程中序遍历其左子树访问根节点中序遍历其右子树后序遍历遍历过程后序遍历其左子树后序遍历其右子树访问根节点我们使用数组来模拟......
  • 欧拉函数
    欧拉函数定义法定义法求欧拉函数是O(sqrt(n))的时间复杂度只可以求单个数的欧拉函数,/*欧拉函数φ的定义,φ(i)表示从[1,i]之间和i互质的数量(a和b互质即gcd(a,b)==1)欧拉函数是积性函数,例如a,b都为质数,那么φ(a*b)=φ(a)*φ(b),递推式为φ(a*b)=......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99