开发一个购物平台需要多少钱,新网站上线 怎么做seo,伊宁网站建设,唐山模板建站系统1. LCA#xff08;最近公共祖先#xff09;
倍增算法的基本思想在前面的博文中有较详细的介绍#xff0c;本文不再复述。此文仅讲解如何使用倍增算法求解多叉树中节点之间的最近公共祖先问题。
什么是最近公共祖先问题#xff1f;
字面而言#xff0c;指在树上查询两个…1. LCA最近公共祖先
倍增算法的基本思想在前面的博文中有较详细的介绍本文不再复述。此文仅讲解如何使用倍增算法求解多叉树中节点之间的最近公共祖先问题。
什么是最近公共祖先问题
字面而言指在树上查询两个也可以是两个以上节点的祖先且是离两个节点最近的祖先。如下图所示
节点 12和节点11的公共祖先有节点4和节点1。节点4是离12和11最近的祖先。即12和11的最近公共祖先是4。也可描述为LCA(12,11)3。 Tips LCA是Lowest Common Ancestor 最近公共祖先的简称。 LCA有如下几个特性 LCA(u)u。单个节点的的最近公共祖先为自己。如上图节点 12的最近公共祖先为 12即LCA(12)12。 如果 u是v的祖先当且仅当LCA(u,v)u。如上图LCA(1,2)1。 如果 u不是v 的祖先并且 v 不是 u 的祖先那么 u,v 分别处于 LCA(u,v) 的两棵不同子树中。如LCA(6,7)3因节点6和节点7 互不为祖先节点6在LCA(6,7)的左子树中节点7在LCA(6,7)的右子树中。 前序遍历中LCA(S) 出现在所有S 中元素之前后序遍历中 LCA(S) 则出现在所有 S 中元素之后。这个很好理解。 两点集并的最近公共祖先为两点集分别的最近公共祖先的最近公共祖先即LCA(A U B )LCA( LCA(A),LCA(B) )。如下图点集A{6,7}则LCA(A)3。点集B{11,12}则LCA(B)8。则cA U B的LCA(c)LCA(3,8)1。利用这个性质可以求解任意多节点之间的最近公共祖先。 两点的最近公共祖先必定处在树上两点间的最短路上。如下图节点9和7之间的最短路径一定经过其最近公共祖先。这个很好理解自行参悟。 d(u,v)h(u)h(v)-2h(LCA(u,v))。其中 d 是树上两点间的距离h 代表某点到树根的距离。即u,v两点之间的距离可以是u到根节点的距离v到根节点的距离- 减去u,v最近公共祖先到根节点的距离*2。如下图所示d(6,7)距离。 2. LCA 朴素算法
知道了什么是LCA后再来了解怎么得到给定的任意 2 点的最近公共祖先。
向上标记法
向上标记法的思想很简单如求节点9和7的最近公共祖先。 先以节点 9也可以选择节点7为起点向上沿着根节点方向查询并一路标记访问过的节点如下图红色节点。 再让节点7向着根节点访问遇到的第一个标记的节点即为LCA(9,7)3。 同步移位法 首先在树上定位u和v的位置。 如果u和v的深度不一样则需要让深度大的节点向上跳跃直到其深度和深度小的节点一致。如查询9和7两节点的祖先。如下图所示9的深度为47的深度为3。先移动指向9的指针让其移动和7深度一致的节点6。然后同时移动两个指针直到遇到相同节点3。 Tips 根节点深度为 1。
使用矩阵存储树信息可以很方便写出相应算法。使用邻接表存储树时为了方便可以为每一个节点设置一个指向父节点的指针。上述算法可统称为朴素算法其特点在于算法实现过程中需要一步一步的移动指针。
本文主要讲解使用培增法求解最近公共祖先。
3. LCA 倍增算法
倍增算法的本质还是补素算法在其基础上改变了向上跳跃的节奏。不采用一步一步向上跳而是以2的幂次方向上跳。比如先跳20步、再跳21步……
也就先跳 1步然后2 步再然后4 步再然后8步再然后16步……
如同前文的同步移位算法思想一样可先让深度大的节点向上跳跳到两个节点的深度一致然后再一起向上跳。
由大到小跳还是由小到大跳
由小到大跳指在移动指针时先移1位再移2位再移 4 位……
下图为由小到大跳的方式实现把指向节点11的指针移到根节点红色标注为其轨迹点。先 201 步到节点8再212步跳到节点 3下一步再跳时越过根节点需要在回溯过程中修正。到达根节点需要跳 3 次。 如下图是由大到小跳的轨迹点跳224步直接到根节点。 如上所述在向上跳跃时采取由大到小的方案更能提升查询性能。也就是说在向上跳跃过程中尽可能一步迈大点。
向上跳几次
现在继续探讨另一个问题一个节点向上跳到其父节点需要跳几次。跳少了肯定是跳不到目标跳多了会越过目标。比如刚才说由节点 11跳到根节点1跳一次就足了。多了无益少了不能到。
如从节点9跳到根节点直观而言可以先跳212步。先到达节点3再跳一步即跳20步便到达了根节点。也就是向上跳2次那么这个2次是如何得知的
答案是根据节点到根节点的深度。
如节点11到根节点的深度为 5一般认定根节点的深度为 1除掉节点本身的深度如果采用朴素算法的一步一步向上跳要向上跳 4次但是使用倍增法向上跳因为 224所以理论上跳一次就可以。
如节点9到根节点的深度为 4除掉本身深度理论是要跳 3次 但是3可以拆分成 2120。倍增法方案可以先跳 2 步再跳 1 步2 次可达目标。
所以要使用倍增算法先要求解出每一个节点在树上的深度。具体可以使用DFS或BFS实现后文再详细介绍。
缓存节点的祖先
为了方便找到节点的祖先可以缓存节点到根节点这条路径上所有的祖先。但是缓存如下图节点 14的祖先时并不是把沿着根节点向上所有祖先13、12、8、4、1都缓存下来。 而是按如下图中的倍增方式缓存仅缓存了13、12、4几个祖先。 因每一个节点都需要缓存其祖先信息显然需要一个二维数组记录这些信息。现设定数组名为 father[i][j]i表示节点的编号j表示 2 的指数。
如 father[14][0]表示节点 14的第 20 个祖先即father[14][0]13。
father[14][1]表示节点 14的第 21 个祖先即father[14][1]12。
father[14][2]表示节点 14的第 22 个祖先即father[14][2]4。
……
那么这些祖先之间有什么样的逻辑关系先画一个线性图观察一下。 如上图所示可得到通过的转移方程式
当 j0时father[i][0]直接父节点。当j0时father[i][j] father[ father[i][j-1]][j-1]。
其实这个道理也简单在以2 倍增的表达式中满足
212020。
222121。
232222。
……
2j2j-12j-1。
所以 i 的 2j-1 级祖先的 2j−1 级祖先就是 i 的 j 级祖先。
具体流程
准备工作到此结束查询任意 2 个节点的最近公共祖先时如果 2 个节点的深度不一样则需要先把 2 个节点深度调整到一样。如下图求解节点5和14的LCA时需要先把节点14向上移动找到和节点5深度一样的祖先节点。 同步深度的流程
计算节点 14和节点5的深度之差节点14深度为 6节点5的深度为3。深度之差为 3。因为 21322 。根据前面缓存信息跳 22步即跳到 father[14][2]4的祖先节点。 因为节点 4的深度小于节点5的深度说明跳过头了。需要减少增量重新以 21 步向上跳。跳到节点12位置。 节点12的深度大于节点5的深度则设置节点12为新起点继续向上跳 201 步。此时节点 8和节点5深度相同。 当 2 个节点的深度一致则继续让 2 个节点同时一起向上跳。如下的节点9、10。 向上跳的策略前文说过从大到小的方向跳。具体实施如下。
两者深度为4因 422。以 j2向上跳则到达根节点之外。 向下减小指数 j的值为 1重新向上跳 212 步。 直观来讲节点3是LCA但是程序不能就此做出判断只能说明找到了公共祖先但是不能说明是LCA。所以还得修正成向上跳 201步。得到 2 个节点的祖先是不相同此时可得到结论节点3是LCA。 总结如下
当跳到的节点是 2 个节点的共同祖先时则需要再减少指数重新跳。当跳到的节点不相同可以再重新计算深度继续向上跳。
知道了节点在树上的深度后如何计算出处于不同深度的节点应该跳多次也就是 j 指数的取值范围
前文举例说明过如果深度为 3 取 3的对数因 21322。向上取整即向上跳 2 次也就是 j 范围为[2,1,0]。可以使用 C math库中提供的 lg函数注意此函数是以 e为底数所以需要进行修改。或者自定义lg生成过程。
可以使用预处理lg数组lg[i]代表深度为i的节点一次性跳多少步可以到达根节点。
for (int i 1; i 10; i)lg[i] lg[i - 1] (1 lg[i - 1] i);可以输出lg[0~100]的值。
0 1 2 2 3 3 3 3 4 4 4 4 4 4 4 4 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 举一个例子如下图所示有 2 个深度为 11的 u和v节点开始同时向上跳。其过程如下所述 根据 lg函数计算深度 11的值因 231124 可得 lg[11]4。这里的 4 表示 j的值即 2 的指数最大值为 4。 这里可以先跳 2416会发现超过根节点其实这里可以先跳 24-18步先到达如下图所示位置。 更新u,v的位置到红色节点标记处然后向上跳 212步。到达根节点位置因相同再减少指数跳 201步到达节点 2位置还是相同因为已经没有指数可以修改。所以节点 2为LCA。
编码实现
DFS搜索。
#include bits/stdc.h
using namespace std;
//边
struct Edge {int t, nex;
} e[500010 1];
//头
int head[500010], tot;void add(int x, int y) {e[tot].t y;e[tot].nex head[x];head[x] tot;
}
//记录节点在树上的深度
int depth[500001];
//记录节点的祖先
int father[500001][30];
//存储对数值
int lg[500001];//now表示当前节点fa表示它的父亲节点
void dfs(int now, int fa) {//记录当前节点的直接父节点father[now][0] fa;//当前节点的深度为父节点深度加 1depth[now] depth[fa] 1;//指数范围为 1 ~ lg[depth[now]]for(int i 1; i lg[depth[now]]; i)//动态转移方程式当前节点的 2^j 祖先是 2^(j-1)祖先的 2^(j-1)祖先father[now][i] father[father[now][i-1]][i-1];//递归深度搜索for(int i head[now]; i; i e[i].nex)if(e[i].t ! fa) dfs(e[i].t, now);
}//LCA 求解
int LCA(int x, int y) {//不妨设x的深度 y的深度if(depth[x] depth[y])swap(x, y);while(depth[x] depth[y])//先跳到同一深度注意 depth[x]-depth[y] ] - 1 避免跳过头x father[x][ lg[ depth[x]-depth[y] ] - 1];if(x y)//如果x是y的祖先那他们的LCA肯定就是x了return x;//按指数由大到小跳for(int k lg[depth[x]] - 1; k 0; --k)if(father[x][k] ! father[y][k])//因为我们要跳到它们LCA的下面一层所以它们肯定不相等如果不相等就跳过去。x father[x][k], y father[y][k];//返回父节点return father[x][0];
}
int main() {
// freopen(bz.in,r,stdin);int n, m, s;scanf(%d%d%d, n, m, s);for(int i 1; i n-1; i) {int x, y;scanf(%d%d, x, y);add(x, y);add(y, x);}//自定义 2 为底数的对数计算 for(int i 1; i n; i)lg[i] lg[i-1] (1 lg[i-1] i);dfs(s, 0);for(int i 1; i m; i) {int x, y;scanf(%d%d,x, y);printf(%d\n, LCA(x, y));}return 0;
}BFS实现。
const int MAXN5e410;
const int DEG20;
struct Edge{int to,next;
}edge[MAXN1];
int head[MAXN],tot;
void addedge(int u,int v){edge[tot](Edge){v,head[u]};head[u]tot;edge[tot](Edge){u,head[v]};head[v]tot;
}
void init(){tot0;memset(head,-1,sizeof(head));
}
int fa[MAXN][DEG];
int dep[MAXN];
void bfs(int r){dep[r]0;fa[r][0]r;queueint Q;Q.push(r);while(!Q.empty()){int uQ.front();Q.pop();for (int i1;iDEG;i)fa[u][i]fa[fa[u][i-1]][i-1];for (int ihead[u];~i;iedge[i].next) {int vedge[i].to;if (vfa[u][0]) continue;dep[v]dep[u]1;fa[v][0]u;Q.push(v);}}
}
int LCA(int u,int v){if (dep[u]dep[v]) swap(u,v);int hudep[u],hvdep[v];int uuu,vvv;for (int dethv-hu,i0;det;det1,i)if(det1) vvfa[vv][i];if (uuvv) return uu;for (int iDEG-1;i0;--i){if (fa[uu][i]fa[vv][i]) continue;uufa[uu][i];vvfa[vv][i];}return fa[uu][0];
}
4. 总结
LCA的求解算法较多本文详细介绍了倍增算法解决 LCA问题中的细枝末节。
