C/C++教程

LCA算法

本文主要是介绍LCA算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

LCA 即最近公共祖先,是指在有根树中,找出某两个结点u和v最近的公共祖先。

在一棵没有环的树上,每个节点肯定有其父亲节点和祖先节点,而最近公共祖先,就是两个节点在这棵树上深度最大公共祖先节点

    换句话说,就是两个点在这棵树上距离最近的公共祖先节点

    所以LCA主要是用来处理当两个点仅有唯一一条确定的最短路径时的路径。

    有人可能会问:那他本身或者其父亲节点是否可以作为祖先节点呢?

    答案是肯定的,很简单,按照人的亲戚观念来说,你的父亲也是你的祖先,而LCA还可以将自己视为祖先节点

   

 常用的求LCA的算法有:Tarjan/DFS+ST/倍增

    后两个算法都是在线算法,也很相似,时间复杂度在O(logn)~O(nlogn)之间,我个人认为较难理解。

    有的题目是可以用线段树来做的,但是其代码量很大,时间复杂度也偏高,在O(n)~O(nlogn)之间,优点在于也是简单粗暴

 

倍增寻找(ST算法): 此算法基于动态规划。   它本质上属于暴力算法的优化版本,只是把暴力算法的一次只跳一步变为了一次跳 2k 步。算法使用数组 fa[i][j] 表示结点 i  的第 2j个父亲,则有递推式

                                                      fa[i][j]=fa[fa[i][j−1]][j−1]

即:结点 i 的第 2 j 个父亲是结点 i ii 的第 2j-1个父亲的第 2j-1  个父亲。

算法对于每一个询问 (u,v),首先将 u 和 v 调整到同一个深度,然后同时向上跳,第一个一样的就是它们的 LCA 。

 实现过程:           1.预处理:通过dfs遍历,记录每个节点到根节点的距离dist[u],深度d[u]           2.init()求出树上每个节点u的2^i祖先p[u][i]           3.求最近公共祖先,根据两个节点的的深度,如不同,向上调整深度大的节点,使得两个节点在同一层上,如果正好是祖先结束,否则,将两个节点同时上   移,查询最近公共祖先。
oid dfs(int u) {
    for(int i=head[u]; i!=-1; i=edge[i].next) {
        int to=edge[i].to;
        if(to==p[u][0])continue;
        d[to]=d[u]+1;
        dist[to]=dist[u]+edge[i].w;
        p[to][0]=u;   //p[i][0]存i的父节点
        dfs(to);
    }
}
void init()//i的2^j祖先就是i的(2^(j-1))祖先的2^(j-1)祖先
{
    for(int j=1; (1<<j)<=n; j++)
        for(int i=1; i<=n; i++)
            p[i][j]=p[p[i][j-1]][j-1];
}
int lca(int a,int b) {
    if(d[a]>d[b])swap(a,b); //b在下面
    int f=d[b]-d[a];              //f是高度差
    for(int i=0; (1<<i)<=f; i++)
        //(1<<i)&f找到f化为2进制后1的位置,移动到相应的位置
        if((1<<i)&f)b=p[b][i];     //比如f=5,二进制就是101,所以首先移动2^0祖先,然后再移动2^2祖先
    if(a!=b) {
        for(int i=(int)log2(N); i>=0; i--)
            if(p[a][i]!=p[b][i])            //从最大祖先开始,判断a,b祖先,是否相同
                a=p[a][i], b=p[b][i];     //如不相同,a b同时向上移动2^j
        a=p[a][0];          //这时a的father就是LCA
    }
    return a;
}

 

 

Tarjan算法(离线算法): 离线算法,是指首先读入所有的询问(求一次LCA叫做一次询问),然后重新组织查询处理顺序以便得到更高效的处理方法。Tarjan算法是一个常见的用于解决LCA问题的离线算法,它结合了深度优先遍历和并查集,整个算法为线性处理时间。

 

在这里插入图片描述

 

 

      该算法的思想为,对于任意一个结点 r  ,处于 r r的不同子树上的两个结点 u ,v ,一定有 LCA(u,v)=r 。这个结论非常显然。首先, r  是 u ,v 的共同祖先;其次,任何深度大于 r 的结点都只会至多存在于 r 的一棵子树中,不可能是既是 u  的祖先又是 v  的祖先,因而 r 是 u , v 的最近公共祖先。

      因此,我们可以暂时忽略询问中 u 和 v  的具体位置,而只是关心它们是否在某结点的不同子树中。我们使用并查集存储不同的子树,对于不在同一个并查集中的两个结点,它们的 LCA  即为这两个并查集的根的 LCA 。需注意,并查集是动态变化的,因为子树的划分有多种,子树也有大小之分。我们应该从下往上、由小到大地将子树一棵棵合并,并在同时更新答案。

       从具体的实现方式来说,算法按照 dfs 序访问和合并结点,当访问到叶子结点 u 时,对于询问 LCA ( u , v ) ,如果 vv 已经被访问过,则用 v  所在并查集的根的祖先更新 LCA ( u , v ) ,然后一边回溯一边合并一边更新。先不着急给出代码,我们使用一开始给出的那张图作为例子,假设我们要询问  (1,2) , (2,5) ,(7,8) , (6,14) , (10,15) 。算法首先遍历 1 → 2 → 5  ,一路上设置 root [ u ] = u  。当发现到叶子了,看询问,发现有一个 (5,2) ,则更新答案 LCA ( 5 , 2 ) = root ( 2 ) = 2 然后回溯,合并 5  和 2 ,更新答案 LCA ( 2 , 5 ) = root ( 5 ) = 2  和 LCA ( 2 , 1 ) = root ( 1 ) = 1

      接着是下一棵子树 3 → 6 → 10 3,同样的把 root 一路设过去,到了 10 。看询问,有个 ( 10 , 15 ) ] ,但 15 没被访问过,直接跳过。回溯,合并 10  和 6,发现有个询问(6,14) ,但 14 也没被访问过,同样跳过。

       然后是子树 11 → 15 , root 设过去,发现询问有 (15,10) ,更新答案 LCA ( 15 , 10 ) = root ( 10 ) = 6 。回溯,合并 15 和 11  。然后, 6  的子树都访问完了,合并 6 , 11 ,不需要更新答案,因为 14 仍然没有访问到。往上, 再合并 6 , 3 ,也没有更新操作。

    接着就是 7 → 12 ,有个 (7,8) 但还没访问,合并。13 ,合并。到了 14 ,终于更新了,答案为 LCA ( 14 , 6 ) = root ( 6 ) = 3 。回溯,合并合并再合并,目前为止, 3的子树和 2  的子树全和 1在同一个并查集里了。

     最后是子树 4 → 8 和 9 ,需要更新的就是 LCA ( 8 , 7 ) = root ( 7 ) = 1  。

Tarjan(u)//marge和find为并查集合并函数和查找函数
{
    for each(u,v)    //访问所有u子节点v
    {
        Tarjan(v);        //继续往下遍历
        marge(u,v);    //合并v到u上
        标记v被访问过;
    }
    for each(u,e)    //访问所有和u有询问关系的e
    {
        如果e被访问过;
        u,e的最近公共祖先为find(e);
    }
}

 

模拟一遍

    假设我们有一组数据 9个节点 8条边 联通情况如下:

    1--2,1--3,2--4,2--5,3--6,5--7,5--8,7--9 即下图所示的树

    设我们要查找最近公共祖先的点为9--8,4--6,7--5,5--3;

    设f[]数组为并查集的父亲节点数组,初始化f[i]=i,vis[]数组为是否访问过的数组,初始为0; 

下面开始模拟过程:

    取1为根节点往下搜索发现有两个儿子2和3;

    先搜2,发现2有两个儿子4和5,先搜索4,发现4没有子节点,则寻找与其有关系的点;

    发现6与4有关系,但是vis[6]=0,即6还没被搜过,所以不操作

    发现没有和4有询问关系的点了,返回此前一次搜索,更新vis[4]=1

    

    表示4已经被搜完,更新f[4]=2,继续搜5,发现5有两个儿子7和8;

    先搜7,发现7有一个子节点9,搜索9,发现没有子节点,寻找与其有关系的点;

    发现8和9有关系,但是vis[8]=0,即8没被搜到过,所以不操作;

    发现没有和9有询问关系的点了,返回此前一次搜索,更新vis[9]=1

    表示9已经被搜完,更新f[9]=7,发现7没有没被搜过的子节点了,寻找与其有关系的点;

    发现5和7有关系,但是vis[5]=0,所以不操作

    发现没有和7有关系的点了,返回此前一次搜索,更新vis[7]=1

    

    表示7已经被搜完,更新f[7]=5,继续搜8,发现8没有子节点,则寻找与其有关系的点;

    发现9与8有关系,此时vis[9]=1,则他们的最近公共祖先find(9)=5

      (find(9)的顺序为f[9]=7-->f[7]=5-->f[5]=5 return 5;)

    发现没有与8有关系的点了,返回此前一次搜索,更新vis[8]=1

 

    表示8已经被搜完,更新f[8]=5,发现5没有没搜过的子节点了,寻找与其有关系的点;

    

    发现7和5有关系,此时vis[7]=1,所以他们的最近公共祖先find(7)=5

      (find(7)的顺序为f[7]=5-->f[5]=5 return 5;)

    又发现5和3有关系,但是vis[3]=0,所以不操作,此时5的子节点全部搜完了;

    返回此前一次搜索,更新vis[5]=1,表示5已经被搜完,更新f[5]=2

    发现2没有未被搜完的子节点,寻找与其有关系的点;

    又发现没有和2有关系的点,则此前一次搜索,更新vis[2]=1

    

    表示2已经被搜完,更新f[2]=1,继续搜3,发现3有一个子节点6;

    搜索6,发现6没有子节点,则寻找与6有关系的点,发现4和6有关系;

    此时vis[4]=1,所以它们的最近公共祖先find(4)=1;

      (find(4)的顺序为f[4]=2-->f[2]=2-->f[1]=1 return 1;)

    发现没有与6有关系的点了,返回此前一次搜索,更新vis[6]=1,表示6已经被搜完了;

    

    更新f[6]=3,发现3没有没被搜过的子节点了,则寻找与3有关系的点;

    发现5和3有关系,此时vis[5]=1,则它们的最近公共祖先find(5)=1

      (find(5)的顺序为f[5]=2-->f[2]=1-->f[1]=1 return 1;)

    发现没有和3有关系的点了,返回此前一次搜索,更新vis[3]=1

    

    更新f[3]=1,发现1没有被搜过的子节点也没有有关系的点,此时可以退出整个dfs了。

这篇关于LCA算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!