【算法】LCA的三种算法

【算法】LCA的三种算法什么是LCALCA(Least Common Ancestors),即最近公共祖先是指在有根树中找出某两个结点x和y最近的公共祖先。三种算法用三种算法可以求解LCA问题分别为朴素算法、倍增算法和Tarjan算法。朴素算法倍增算法和Tarjan算法都在建立在朴素算法的思想下因此了解朴素算法的思想有助于更好的理解进阶算法。朴素算法前置知识邻接表dfs。假设我们要寻找某两个节点x和y的LCA那么我们肯定是让深度更深的那个结点跳到另一个结点深度处然后再让这两个结点一起向上跳直到首次相遇。光说可以有些抽象举个例子就以下面这张图中的树为例。图中结点4先跳到结点3的位置然后两个结点一起向上跳随后跳到结点1处相遇所以结点2和结点4的LCA为结点1。也就是说我们只要记录下每个结点的深度信息和祖先信息就能通过逐个向上跳跃直至相遇来确定两个结点的LCA。这便是LCA朴素算法的核心支撑所在但是由于朴素算法每次跳跃一层因此他的时间复杂度很差尤其是当树退化为链的时候那么如果我们让他跳跃多层是不是可以更好更快的解决问题呢答案是一定的而接下来的倍增算法就是这个思想。倍增算法倍增算法前置知识邻接表DP倍增dfs。倍增算法我们将会定义一个数组fa[i][j]表示结点i向上跳2j层所到的结点从而实现了倍增跳跃而且通过有限的组合跳跃我们到达任意结点处。例如向上5层我们可以先向上跳跃22层之后再向上跳跃2^0次方。同时我们可以证明又fa[x][i] fa[fa[x][i-1]][i-1],实质就是2^(i-1) 2^(i-1) 2^i.同时倍增LCA算法中还用到了贪心的思想假如现在有两个结点xy假设x深度更大则我们要尽可能地让x在不超过y的深度的前提下尽可能地接近y也就是跨的步子尽可能大这样操作过后结点x与结点y的深度就一定相同了。相同之后如果已经重合直接return如果没有那么现在两个结点处于一个平行的位置。接下来我们让两个结点同时向上跳也是能跳多大就跳多大但是肯定是有限制的就像上一步一样这个限制就是只有在跳完之后他们结点不重合时才跳。这个地方有点绕不要急我们结合代码看一下。点击查看代码int lca(int u, int v) { if(depth[u] depth[v]) swap(u, v); for(int i MAXLOG - 1; i 0; i--) { if(depth[u] - (1 i) depth[v]) { u parent[u][i]; } } if(u v) return u; // 注意看这里这一步是平行之后的操作 for(int i MAXLOG - 1; i 0; i--) { if(parent[u][i] ! parent[v][i]) { u parent[u][i]; v parent[v][i]; } } return parent[u][0]; }我们注意到在平行之后只要在parent[u][i] ! parent[v][i]的前提下尽可能地大跨步就能保证跳到最近的公共祖先的前一个位置这个位置上面一层也就是2^0方层就是公共祖先同时也是最近的公共祖先。Tarjan算法Tarjan算法前置知识邻接表并查集dfs。Tarjan巧妙地将并查集和dfs结合在一起实现了将单次查询地时间复杂度降到了常数级别的离线算法具体步骤如下对于每个节点u初始化u的祖先为u本身并标记u为已访问。对于每条边(u,v)/* 如果v未被访问则对v进行深度优先搜索并将v的祖先设置为u。/* 如果v已经被访问那么u和v的最近公共祖先就是u的祖先和v的祖先的最小值。在查询LCA问题时/* 对于每个查询(q, u, v)其中q为查询编号u和v分别为查询的两个节点/* 如果(u,v)已经被访问过那么查询结果为(u,v)的最近公共祖先。/* 如果(u,v)未被访问过那么查询结果为(u,v)的最近公共祖先的祖先。总结–离线用Tarjan在线用倍增。《网络安全从零到精通全套学习大礼包》96节从入门到精通的全套视频教程免费领取如果你也想通过学网络安全技术去帮助就业和转行我可以把我自己亲自录制的96节 从零基础到精通的视频教程以及配套学习资料无偿分享给你。网络安全学习路线图想要学习 网络安全作为新手一定要先按照路线图学习方向不对努力白费。对于从来没有接触过网络安全的同学我帮大家准备了从零基础到精通学习成长路线图以及学习规划。可以说是最科学最系统的学习路线大家跟着这个路线图学习准没错。配套实战项目/源码所有视频教程所涉及的实战项目和项目源码学习电子书籍学习网络安全必看的书籍和文章的PDF市面上网络安全书籍确实太多了这些是我精选出来的面试真题/经验以上资料如何领取以上资料如何领取