【算法与数据结构】——LCA

亦凉 2022-08-29 15:50 70阅读 0赞

# 最近公共祖先LCA #

最近公共祖先指有根树中距离两个节点最近的公共祖先。祖先指从当前节点到树根路径上的所有节点。

# 暴力搜索法 #

### 向上标记法 ###

顺着树向上逐步标记，若两节点都标记了同一点，则这一点就是LCA(u,v)

### 同步前进法 ###

将u，v中较深的节点向上走到与较浅的节点同一深度，然后两个点一起向上走，知道走到同一个节点

# 树上倍增法 #

### 原理 ###

F\[i,j\]表示i的 2 j 2^j 2j辈祖先，即i节点向根节点走 2 j 2^j 2j步到达的节点。  
F\[i,j\]可以分为两个步骤，i节点先向根节点走 2 j − 1 2^\{j-1\} 2j−1步得到F\[i,j-1\];再从F\[i,j-1\]节点出发想根节点走 2 j − 1 2^\{j-1\} 2j−1步，得到F\[F\[i,j-1\],j-1\],该节点为F\[i,j\]。

### 求解步骤 ###

首先让深度大的节点y向上走到与x同一深度，然后xy一起向上走。和暴力搜索不同的是向上走是按照倍增思路走的。

### 算法实现 ###

ST_create()
    { 
    for(int j = 1;j <= k;j++)
    { 
    for(int i = 1;i <= n;i++)
    { 
    f[i][j]=f[f[i][j-1]][j-1];
    }
    }
    }
    int LCA_st_query(int x,int y)//求x，y的最近公共祖先。
    { 
    if（d[x]>d[y])
    { 
    swap(x,y)
    }
    for(i = k;i>=0;i--)//y向上走到同一深度
    { 
    if(d[f[y][i]]>=d[x])
    { 
    y=f[y][i];
    }
    if(x==y)
    return x;
    for(int i = k;i>=0;i--)
    { 
    if(f[x][i]!=f[y][i])
    { 
    x = f[x][i];
    y = f[y][i];
    }
    return f[x][0];

# 在线RMQ算法 #

### 原理 ###

两个节点的LCA一定是两个节点之间欧拉序列中深度最小的节点，寻找深度最小值 时可以使用RMQ算法。  
欧拉序列指的是在深度遍历过程中把依次经过的节点记录下来，把回溯时经过的节点也记录下来，一个节点可能被记录多次，相当于按照左中右的顺序进行进行深度遍历得到的序列。

### 算法实现 ###

*  深度遍历，得到3个数组：首次出现的下标pos\[\],深度遍历得到的欧拉序列seq\[\],深度deq\[\];

void dfs(int u,int d){ //dfs序列
    vis[u]=true;
    pos[u]=++tot;
    seq[tot]=u;
    deq[tot] = d;
    for(int i = head[u];i;i=e[i].next)
    { int v=e[i].to;
    w=e[i].next;
    if(vis[v])
    continue;
    dist[v]=dist[u]+w;
    dfs(v,d+1);
    seq[++tot]=u;
    dep[tot]=d;
    }
    }

*  根据欧拉序列的深度创建区间最值查询的ST，F\[i\]\[j\]表示\[i,i+ 2 j 2^j 2j\-1\]区间深度最小的节点下标。

void ST_create()
    { 
    for(int i =1;i<tot;i++)//初始化
    { f[i][0]=i;//记录下标不是最小深度
    }
    int k = log2(tot);
    for(int i = 1;i <= tot-(1<<j)+1;i++)
    { 
    if(dep[f[i][j-1])(dep[f[i+(1<<(j-1))][j-1]])
    F[i][j]=f[i][j-1];
    else
    f[i][j]=f[i+(1<<(j-1))][j-1];
    }

*  查询\[l,r\]区间深度最小的节点下标，与RMQ区间查询类似。

int RMQ_query(int l,int r){ //查询[l,r]的区间最值
    int k=log2(r-l+1);
    if(dep[f[l][k]]<dep[f[r-(1<<k)+1][k]])
    return f[l][k];
    else
    return f[r-(1<<k)+1][k];

*  求x,y的最近公共祖先，先得到x，y首次出现在欧拉序列中的下标，然后查询该区间深度最小的节点的下标，根据下标读取欧拉序列的节点即可。

int LCA(int x,int y)
    { 
    int l = pos[x];
    int r = pos[y];
    if(l>r)
    { 
    swap(l,r);
    }
    return seq[RMQ_query(l,r)];//返回节点
    }

# Tarjan算法 #

## 思路 ##

*  初始化集合号数组和访问数组，fa\[i\]=i,vis\[i\]=0;
 *  从u出发深度优先遍历，标记vis\[u\]=1,深度优先遍历u所有未被访问的邻接点，在遍历过程中更新距离，回退时更新集合号。
 *  当u的邻接点全部遍历完毕时，检查关于u的所有查询，若存在一个查询u，v，而vis\[v\]=1，则利用并查集查找v的祖宗，找到的节点就是u，v的最近公共祖先。

## 算法实现 ##

int find(int x)//并查集查找祖宗
    { 
    if(x!=fa[x])
    { x=find(fa[x]);
    }
    return fa[x];
    }
    
    void tarjan(int u)//tarjan算法
    { 
    vis[u] = 1;
    for(int i = head[u];i;i=e[i].next)
    { 
    int v=e[i].to,w=e[i].c;
    if(vis[v])
    continue;
    dis[v]=dis[u]+v;
    tarjan(v);
    fa[v]=u;
    }
    for(int i = 0;i < query[u].size();i++)
    { int v=query[u][i];
    int id = query_id[u][i];
    if(vis[y]){ 
    int lca=find(v);
    ans[id]=dis[u]+dis[v]-2*dis[lca];
    }
    }
    }