图论：倍增求解最近公共祖先LCA

图论：倍增求解最近公共祖先LCA

引用

CSDN

1.

https://m.blog.csdn.net/zpf123456789zpf/article/details/139443670

最近公共祖先（LCA）是图论中的一个重要概念，在算法竞赛和实际应用中都有广泛的应用。本文将详细介绍如何使用倍增算法高效地求解LCA问题，包括基本概念、朴素算法和优化后的倍增算法，并提供完整的代码实现。

引入

树是一种特殊的图，你是否想过这样一个问题：给你一棵多叉树，随机给出两个节点，如何求解这两个节点的最近公共祖先？

模板题目链接：
https://www.luogu.com.cn/problem/P3379

基本概念

树的深度：给节点分层，根节点为第一层，即深度为1，依次类推，如图：
节点深度通过depth数组记录，如上图的depth数组如下:

朴素算法

Step1：深度优先搜索填充深度和父节点数组

首先通过深度优先搜索（DFS）遍历整棵树，填充节点深度数组depth和父节点数组fa。代码如下：

// u表示当前节点，father表示u的父节点
void dfs(int u, int father) {
    depth[u] = depth[father]+1;  // 当前节点深度等于父节点深度+1
    fa[u] = father;   // 记录u父节点
    for(int ne : g[u])  {  // 遍历所有孩子节点，并递归填充depth和fa数组
        if(ne != father) dfs(ne, u); // 除了自己的父节点，其他节点都递归搜索
    }
}  

Step2：求解两个节点的最近公共祖先

最朴素的想法是，找出两个节点中深度最大的那个节点，让其向上移动，直到两个节点的深度一样（即在同一层），此时停止，然后两个节点一起向上移动，直到两个节点的父节点为同一个节点即可得到最近公共祖先。代码如下：

// 寻找u和v的LCA
int lcaBaoli(int u, int v) {
    if(depth[u] < depth[v]) swap(u, v);  // 让u永远指向最深的节点
    while(depth[u] > depth[v]) u = fa[u];  // 只要u的深度大于v，那就让u一直往上爬，直到两者在同一层停止就行
    if(u == v) return u;  // 在同一层了，先判断是不是同一个节点，如果是直接返回
    while(fa[u] != fa[v]) {  // u和v的父节点不是同一节点时
        u = fa[u], v = fa[v]; // 让u和v一起向上爬，此时u和v一定处于同一层中
    }
    return fa[u];  // 此时u的父节点和v的父节点是同一个节点，因此直接返回即可
}

完整代码

#include "bits/stdc++.h"
using namespace std;
const int N = 500000+9;
int n, m, s, x, y;
vector<int> g[N];
int depth[N];  // depth[u] 表示节点u的深度
int fa[N];  

// 寻找u和v的LCA
int lcaBaoli(int u, int v) {
    if(depth[u] < depth[v]) swap(u, v);  // 让u永远指向最深的节点
    while(depth[u] > depth[v]) u = fa[u];  // 只要u的深度大于v，那就让u一直往上爬，直到两者在同一层停止就行
    if(u == v) return u;  // 在同一层了，先判断是不是同一个节点，如果是直接返回
    while(fa[u] != fa[v]) {  // u和v的父节点不是同一节点时
        u = fa[u], v = fa[v]; // 让u和v一起向上爬，此时u和v一定处于同一层中
    }
    return fa[u];  // 此时u的父节点和v的父节点是同一个节点，因此直接返回即可
}

// u表示当前节点，father表示u的父节点
void dfs(int u, int father) {
    depth[u] = depth[father]+1;  // 当前节点深度等于父节点深度+1
    fa[u] = father;   // 记录u父节点为father
    for(int ne : g[u])  {  // 遍历所有孩子节点，并递归填充depth和fa数组
        if(ne != father) dfs(ne, u); // 除了自己的父节点，其他节点都递归搜索
    }
}

int main() {
    scanf("%d%d%d", &n, &m, &s);
    for(int i=1; i<n; i++) {
        scanf("%d%d", &x, &y);
        g[x].push_back(y); // 建成无向图
        g[y].push_back(x);
    }
    dfs(s, 0); // 通过深搜填充depth数组和p数组
    while(m--) {
        scanf("%d%d", &x, &y);
        printf("%d\n", lcaBaoli(x, y));
    }
    return 0;
}  

结果如下：

优化思路

以上朴素算法虽然可以解决问题，但效率较低。我们可以借鉴ST表和并查集路径压缩的思想进行优化。具体来说，我们可以记录每个节点的不同层级的祖先，按照距离进行划分，距离为1表示上一级祖先（爸爸），距离为2表示上两级祖先（爷爷），距离为4表示上四级祖先（爷爷的爷爷）等。

倍增算法

算法思想

倍增思想的核心是通过预处理，记录每个节点的2^i级祖先。具体来说，fa[u][i]表示节点u的上2^i级祖先。通过这种方式，我们可以快速定位两个节点的最近公共祖先。

预处理代码如下：

// u表示当前节点，father表示u的父节点
void dfs(int u, int father) {
    depth[u] = depth[father]+1;  // 当前节点深度等于父节点深度+1
    fa[u][0] = father;   // 当前节点向上2^0=1个祖先为当前的父节点
    for(int i=1; i<=19; i++) {  //向上找到1,2,4,8,....,2^19长度的祖先并填充
        fa[u][i] = fa[fa[u][i-1]][i-1];  // 该递推式是核心
    }
    for(int ne : g[u])  {  // 遍历所有孩子节点，并递归填充depth和p数组
        if(ne != father) dfs(ne, u); // 除了自己的父节点，其他节点都递归搜索
    }
}  

查找最近公共祖先的核心代码如下：

// lcaMultiply 函数返回u和v的父节点
int lcaMultiply(int u, int v) {  // 倍增
    if(depth[u] < depth[v]) swap(u, v);  // 让u指向深度最大的节点
    for(int i=19; i>=0; i--) { // 向上找u的祖先，通过数学可以推出来，最终u和v的深度一定会相等，因为两者深度差为一个大于等于0的数，如果等于0什么都不做，对于大于0的数，一定可以通过1，2，4，8，16，32，...，凑出来
        if(depth[fa[u][i]] >= depth[v]) {  
            u = fa[u][i];
        }
    }
    if(u == v) return u;  // 如果此时u和v刚好相等，那一定是最近的公共祖先，直接返回即可，
    for(int i=19; i>=0; i--) {  // 两个一起往上找祖先，
        if(fa[u][i] != fa[v][i]) {    // 如果两个祖先不一样，就继续往上走
            u = fa[u][i];  // 向上走到祖先
            v = fa[v][i];
        }
    }
    return fa[u][0];
}  

完整代码

#include "bits/stdc++.h"
using namespace std;
const int N = 500000+9;
int n, m, s, x, y;
vector<int> g[N];
int depth[N];  // depth[u] 表示节点u的深度
int fa[N][20];  // fa[u][i]表示节点u向上的2^i个父节点，比如000->111->222->333->444,则fa[444][0]为333，fa[444][1]为222, fa[444][2]为000

// lcaMultiply 函数返回u和v的父节点
int lcaMultiply(int u, int v) {  // 倍增
    if(depth[u] < depth[v]) swap(u, v);  // 让u指向深度最大的节点
    for(int i=19; i>=0; i--) { // 向上找u的祖先，通过数学可以推出来，最终u和v的深度一定会相等，因为两者深度差为一个大于等于0的数，如果等于0什么都不做，对于大于0的数，一定可以通过1，2，4，8，16，32，...，凑出来
        if(depth[fa[u][i]] >= depth[v]) {  
            u = fa[u][i];
        }
    }
    if(u == v) return u;  // 如果此时u和v刚好相等，那一定是最近的公共祖先，直接返回即可，
    for(int i=19; i>=0; i--) {  // 两个一起往上找祖先，
        if(fa[u][i] != fa[v][i]) {    // 如果两个祖先不一样，就继续往上走
            u = fa[u][i];  // 向上走到祖先
            v = fa[v][i];
        }
    }
    return fa[u][0];
}

// u表示当前节点，father表示u的父节点
void dfs(int u, int father) {
    depth[u] = depth[father]+1;  // 当前节点深度等于父节点深度+1
    fa[u][0] = father;   // 当前节点向上2^0=1个祖先为当前的父节点
    for(int i=1; i<=19; i++) {  //向上找到1,2,4,8,....,2^19长度的祖先并填充
        fa[u][i] = fa[fa[u][i-1]][i-1];  // 该递推式是核心
    }
    for(int ne : g[u])  {  // 遍历所有孩子节点，并递归填充depth和p数组
        if(ne != father) dfs(ne, u); // 除了自己的父节点，其他节点都递归搜索
    }
}

int main() {
    scanf("%d%d%d", &n, &m, &s);
    for(int i=1; i<n; i++) {
        scanf("%d%d", &x, &y);
        g[x].push_back(y); // 建成无向图
        g[y].push_back(x);
    }
    dfs(s, 0); // 通过深搜填充depth数组和p数组
    while(m--) {
        scanf("%d%d", &x, &y);
        printf("%d\n", lcaMultiply(x, y));
    }
    return 0;
}

通过倍增算法，我们可以将LCA问题的时间复杂度优化到O(logn)，大大提高了算法的效率。