建设网站哪间公司比较好,网站开发时如何设计英文版本,答辩学网站开发,oecms(php企业网站管理系统)1. DFS 序和时间戳
1.1 DFS 序
定义#xff1a;树的每一个节点在深度优先遍历中进、出栈的时间序列。
如下树的 dfs 序就是[1,2,8,8,5,5,2,4,3,9,9,3,6,6,4,7,7,1]。 下图为生成DFS的过程。对于一棵树进行DFS序#xff0c;除了进入当前节点时对此节点进行记录#xff0c;…1. DFS 序和时间戳
1.1 DFS 序
定义树的每一个节点在深度优先遍历中进、出栈的时间序列。
如下树的 dfs 序就是[1,2,8,8,5,5,2,4,3,9,9,3,6,6,4,7,7,1]。 下图为生成DFS的过程。对于一棵树进行DFS序除了进入当前节点时对此节点进行记录同时在回溯到当前节点时对其也记录一下所以DFS序中一个节点的信息会出现两次。 Tips 因为在树上深度搜索时可以选择从任一节点开始所以DFS序不是唯一的。 DFS序的特点 可以把树数据结构转换为线性数据结构从而可以把基于线性数据的算法间接用于处理树上的问题。堪称降维打击。 相同编号之间的节点编号为以此编号为根节点的子树上的所有节点编号。 [2,8,8,5,5,2]表示编号 2为根节点的子树中所有节点为8,5。 [4,3,9,9,3,6,6,4]表示编号 4为根节点的子树中所有节点为 3,9,6。 如果一个节点的编号连续相同则此节点为叶节点。 树的DFS序的长度是2NN表示节点的数量。 求DFS序的代码
#include cstdio
using namespace std;
const int maxn1e510;
int n;
int tot,to[maxn1],nxt[maxn1],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 ihead[x];i;inxt[i]){int yto[i];if(yf)continue;dfs(y,x);}id[cnt]x;
}
int main()
{scanf(%d,n);for(int i1;in;i){int x,y;scanf(%d%d,x,y);add(x,y);add(y,x);}dfs(1,0);for(int i1;icnt;i)printf(%d ,id[i]);return 0;
}测试数据
9
1 2
1 4
1 7
2 8
2 5
4 3
4 6
3 91.2 时间戳
按照深度优先遍历的过程按每个节点第一次被访问的顺序依次给予这些节点1−N的标记这个标记就是时间戳。如果一个点的起始时间和终结时间被另一个点包括这个点肯定是另一个点的子节点简称括号化定理。每棵子树 x 在 DFS 序列中一定是连续的一段结点 x 一定在这段的开头。 dfs与时间戳的关系对应列表中索引号和值的关系。 在dfs代码中添加进入节点时的顺序和离开节点时的顺序。
//……
//in 开始时间 out 结束时间
int in[maxn],out[maxn];
//……
void dfs(int x,int f) {//节点的 dfs 序id[cnt]x;//开始时间in[x]cnt;for(int ihead[x]; i; inxt[i]) {int yto[i];if(yf)continue;dfs(y,x);}id[cnt]x;//结束时间out[x]cnt;
}
//……3. DFS 序的应用
3.1 割点
什么是割点
如果去掉一个节点以及与它连接的边该点原来所在的图被分成两部分则称该点为割点。如下图所示删除 2号节点剩下的节点之间就不能两两相互到达了。例如 4号不能到5号6号也不能到达1号等等。一个连通分量变成两个连通分量 怎么判断图是否存在割点以及如何找出图的割点
Tarjan 算法是图论中非常实用且常用的算法之一能解决强连通分量、双连通分量、割点和割边桥、求最近公共祖先LCA等问题。
Tarjan算法求解割点的核心理念
在深度优先遍历算法访问到k点时此时图会被k点分割成已经被访问过的点和没有被访问过的点。如果k点是割点则没有被访问过的点中至少会有一个点在不经过k点的情况下是无论如何再也回不到已访问过的点了。则可证明k点是割点。
下图是深度优先遍历访问到2号顶点的时候。没有被访问到的顶点有4、5、6号顶点。 Tips 节点边上的数字表示时间戳。 其中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的父节点。 搜索到4号时与4号相连的边有4-14-1是没有访问过的边且1号节点已经标记过访问过也就是说通过4号点又回到了1号点。所以说4-1是一条回边或者说 1-……-4之间存在一个环。则4号点的 low[4]min( low[4],dfn[1] )1 因为 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])。 继续更新5、6号节点的low值。 根据这些信息如何判断割点。
如果当前点为根节点时若子树数量大于一则说明该点为割点子树数量不等于与该点连接的边数。如果当前点不为根节点若存在一个儿子节点的low值大于或等于该点的dfn值时low[子节点] dfn[父节点]该点为割点即子节点无法通过回边到达某一部分节点这些节点的dfn值小于父亲节点。这个道理是很好理解的说明子节点想重回树的根节点是无法绕开父节点。
3.2 割边
定义即在一个无向连通图中如果删除某条边后图不再连通。如下图删除2-5和5-6后图不再具有连通性。
删除2-5和5-6边后。 那么如何求割边呢
只需要将求割点的算法修改一个符号就可以。只需将low[v]num[u]改为low[v]num[u]取消一个等于号即可。因为low[vnum[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];
vectorint 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到的时候加进一次回去的时候也加进。 性质 节点 x 第一次出现与最后一次出现的位置之间的节点均为 x 的子节点 任意两个节点的 LCA 是欧拉序中两节点第一次出现位置中深度最小的节点。两个节点第一次出现的位置之间一定有它们的LCA并且这个LCA一定是这个区间中深度最小的点。
根据欧拉序的性质可以用来求解CLA。如上图求解 LCA(9,6)。
在欧拉序中找到9和6第一次出现的位置。 直观比较知道4号节点是其LCA特征是9和6之间深度最小的节点。
欧拉序求LCA先求图的欧拉序、时间戳可以记录进入和离开节点的时间以及节点深度。有了这些信息理论上足以求出任意两点的LCA。变成了典型的RMQ问题。 为了提升多次查询性能可以使用ST表根据节点的深度缓存节点的信息。j0时如下图所示。 j1表示区间长度为 2值为区间长度为 1的两个子区间的深度值小的节点。 欧拉序求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];
vectorint 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(vfa)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 ];}coutendl;}
}int getlca(int u, int v) {if(dfn[u]dfn[v])swap(u,v);udfn[u],vdfn[v];int dlg2[v-u1];int f1st[ u ][d ];int f2st[v-(1d)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;cinuv;int resgetlca(u,v);cout res;return 0;
}5. 总结
DFS序和欧拉序并不难理解正如四两拨千斤却能解决很多复杂的问题。
