倍增算法-最大公共祖先

难度系数：4
适用范围：入门级

“倍增”是一个用途极其广泛的算法，是由“分治、递归”算法延伸推广出的一种处理问题的极其常用的思想，可以解决如快速幂、求LCA（最近公共祖先）、O(1)求区间极值、求后缀数组……等一系列问题。

倍增法求LCA

/**************************************************************** 
 * Description: LCA implementation with binary lifting
 * Author: Alex Li
 * Date: 2023-06-12 08:36:14
 * LastEditTime: 2024-05-09 19:43:24
****************************************************************/

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int l; //树的高度的对数值，用于LCA查询。
const int MAX_SIZE=10001; //树的最大节点数，设置为10001
//MAX_DEPTH每个节点需要存储祖先的最大深度，设定为16。理论上，对于10000个节点的树，
//深度至多需要约14（因为2^14≈16384),但这里取了16作为保险。
const int MAX_DEPTH=16;  
//使用动态数组的方式存储每个节点的邻接节点列表，实现了树的图形结构。
vector<int>  graph[MAX_SIZE]; 
//存储每个节点的深度。
int depth[MAX_SIZE]; 
//存储每个节点在不同 2 的幂次的祖先。
int fathers[MAX_SIZE][MAX_DEPTH]; 


int N;//结点数

//深度优先搜索（DFS）函数，节点遍历用于构建树结构中的fathers[][]数组。
//两个参数：当前正在访问的节点 node 和该节点的父节点 father。
void DFS(int node, int father){   
    
    depth[node]=depth[father]+1; //设定当前节点的深度为父节点深度加1。
    fathers[node][0]=father; //记录当前节点的直接父节点（即2^0级祖先）。
    //建立祖先的表,fatthers[node][i]是指node结点向上第2^i层的祖先结点
    for(int i=1;i<depth[node];i++)
        fathers[node][i]=fathers[fathers[node][i-1]][i-1];
    int cnt=graph[node].size();
    //把node结点在graph表中所有结点(除父结点外)深搜遍历
    for (int i = 0; i <cnt; i++){
        if(father!=graph[node][i])
            DFS(graph[node][i],node);
    }
}

int LCA(int a, int b){
    //这里检查两个节点的深度，确保 a 是更深的节点（或者它们的深度相同）。
    if (depth[a] < depth[b]) {
        swap(a, b);
    }
    //循环是为了将节点 a 向上提升到与节点 b 同一深度。通过2^i级的跳跃来迅速减小深度差，这样可以高效地调整 a 的位置。
    for (int i = l; i >= 0; i --) {
        if (depth[a]-(1<<i) >= depth[b]) {
            a = fathers[a][i];
        }
    }
    if (a == b) return a;
    //两个结点一起向上跳，先跳大的，再跳小的。
    for (int i = l ; i >= 0; i --) {
    //如果两个结点的father一样，哪就从重跳小的，如果不一样，哪就把两个结点移动到新高度。
        if (fathers[a][i] != 0 && fathers[a][i] != fathers[b][i]) {
            a = fathers[a][i];
            b = fathers[b][i];
        }
    }
    return fathers[a][0];
}
int main(){
    int r,a,b;
    cout<<"please input the number of Node and No. of root Node: ";
    cin>>N>>r;
    //用于计算在倍增方法中所需存储每个节点的最大跳跃深度，
    l=ceil(log2(N));
    cout<<'\n';
    cout<<"input edge: "<<'\n';
    for(int i=1;i<=N-1;i++){
        cin>>a>>b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    DFS(r,0); // r是根结点编号，, 根结点的父结点为0
    cout<<"please input two node which you want to know LCA: ";
    cin>>a>>b;
    cout<<"the LCA of "<<a<<" and "<<b<<" is "<<LCA(a,b);
}

P3379

Previous Topic

Back to Lesson

Next Topic

数据结构与算法

倍增算法-最大公共祖先