複製鏈接
請複製以下鏈接發送給好友
https://baike.baidu.hk/item/最近公共祖先/8918834
複製
複製成功

最近公共祖先

鎖定
對於有根樹T的兩個結點u、v，最近公共祖先LCA(T,u,v)表示一個結點x，滿足x是u和v的祖先且x的深度盡可能大。在這裏，一個節點也可以是它自己的祖先。
中文名
最近公共祖先
外文名
Lowest Common Ancestors
簡    稱
LCA
算    法
離線算法，倍增法

目錄

  1. 1 算法簡介
  2. 2 算法
  3. 3 算法實例

最近公共祖先算法簡介

另一種理解方式是把T理解為一個無向無環圖，而LCA(T,u,v)即u到v的最短路上深度最小的點。
這裏給出一個LCA的例子：
對於T=<V,E>
V={1,2,3,4,5}
E={(1,2),(1,3),(3,4),(3,5)}
則有：
LCA(T,5,2)=1
LCA(T,3,4)=3
LCA(T,4,5)=3

最近公共祖先算法

離線算法 Tarjan
利用並查集優越的時空複雜度，我們可以實現LCA問題的O(n+Q)算法，這裏Q表示詢問的次數。
Tarjan算法基於深度優先搜索的框架，對於新搜索到 的一個結點，首先創建由這個結點構成的集合，再對當前結點的每一個子樹進行搜索，每搜索完一棵子樹，則可確定子樹內的LCA詢問都已解決。其他的LCA詢問的結果必然在這個子樹之外，這時把子樹所形成的集合與當前結點的集合合併，並將當前結點設為這個集合的祖先。
之後繼續搜索下一棵子樹，直到當前結點的所 有子樹搜索完。這時把當前結點也設為已被檢查過的，同時可以處理有關當前結點的LCA詢問，如果有一個從當前結點到結點v的詢問，且v已被檢查過，則由於 進行的是深度優先搜索，當前結點與v的最近公共祖先一定還沒有被檢查，而這個最近公共祖先的包涵v的子樹一定已經搜索過了，那麼這個最近公共祖先一定是v 所在集合的祖先。
下面給出這個算法的偽代碼描述：
LCA(u){
Make-Set(u)
ancestor[Find-Set(u)]=u
對於u的每一個孩子v{
LCA(v)
Union(u)
ancestor[Find-Set(u)]=u
}
checked[u]=true
對於每個(u,v)屬於P{
ifchecked[v]=true
then回答u和v的最近公共祖先為ancestor[Find-Set(v)]
}
}
由於是基於深度優先搜索的算法，只要調用LCA(root[T])就可以回答所有的提問了，這裏root[T]表示樹T的根，假設所有詢問(u,v)構成集合P。
在線算法 倍增法
每次詢問O(logN)
d[i] 表示 i節點的深度， p[i,,j] 表示 i 的 2^j 倍祖先
那麼就有一個遞推式子 p[i,,j]=p[p[i,,j-1],,j-1]
這樣子一個O(NlogN)的預處理求出每個節點的 2^k 的祖先
然後對於每一個詢問的點對(a, b)的最近公共祖先就是：
先判斷是否 d[a] ＞ d[b] ,如果是的話就交換一下(保證 a 的深度小於 b 方便下面的操作)，然後把b 調到與a 同深度, 同深度以後再把a, b 同時往上調(dec(j)) 調到有一個最小的j 滿足p[a,,j]!=p[b,,j] (a b 是在不斷更新的), 最後再把 a, b 往上調 (a=p[a,0], b=p[b,0]) 一個一個向上調直到a = b, 這時 a or b 就是他們的最近公共祖先。

最近公共祖先算法實例

問題描述：
設計一個算法，對於給定的樹中 結點返回它們的最近公共祖先。
編程任務：
對於給定的樹和樹中結點對，計算結點對的最近公共祖先。
數據輸入：
由文件input.txt給出輸入數據。
第一行有1個正整數n，表示給定的樹有n個頂點，編0號為1，2，…，n。編號為1 的頂點是樹根。接下來的n 行中，第i+1 行描述與i 個頂點相關聯的子結點的信息。每行的第一個正整數k表示該頂點的兒子結點數。其後k個數中，每1 個數表示1 個兒子結點的編號。當k=0 時表示相應的結點是葉結點。文件的第n+2 行是1 個正整數m，表示要計算最近公共祖先的m個結點對。接下來的m行，每行2 個正整數，是要計算最近公共祖先的結點編號。
結果輸出:
將編程計算出的m個結點對的最近公共祖先結點編號輸出到文件output.txt。每行3 個
正整數，前2 個是結點對編號，第3 個是它們的最近公共祖先結點編號。
輸入文件示例(input.txt)
12
3 2 3 4
2 5 6
0
0
2 7 8
2 9 10
0
0
0
2 11 12
0
0
5
3 11
7 12
4 8
9 12
8 10
輸出文件示例(output.txt)
3 11 1
7 12 2
4 8 1
9 12 6
8 10 2
C代碼實現：
#include<iostream>
#include<fstream>
using namespace std;
inline void Swap(int&a,int&b){
    int temp=a;
    a=b;
    b=temp;
}
int Partition(int *a,int p,int r){
    int i=p;
    int j=r+1;
    int x=a[p];
    while(true){
        while(a[++i]<x&&i<r);
        while(a[--j]>x);
        if(i>=j) break;
        Swap(a[i],a[j]);
    }
    a[p]=a[j];
    a[j]=x;
    return j;
}
void QuickSort(int *a,int p,int r){
    if(p<r){
        int q=Partition(a,p,r);
        QuickSort(a,p,q-1);
        QuickSort(a,q+1,r);
    }
}
int FindSource(int *array,int source,int low,int high){
    int mid;
    while(low<=high){
        mid=(low+high)/2;
        if(source==array[mid]) return source;
        else{
            if(source<array[mid]) high=mid-1;
            else low=mid+1;
        }
    }
    return -1;
}
class CommonTree{
    public:
        CommonTree(int Max=10);
        ~CommonTree();
        void getdata(int *treedata,int num);
        int find_same_ancestor(int Node1,int Node2,int array_num);
        void getroot(int i);
        int Size();
        void Print()
        const;
    private:
        int *TreeArray;
        int size;
        int root;
};/
CommonTree::CommonTree(int Max){
    size=Max;
    TreeArray=newint[size];
    if (TreeArray==NULL) exit(1);
}
CommonTree::~CommonTree(){
    delete[]TreeArray;
}
voidCommonTree::getdata(int*treedata,intnum){
    int *p_temp=TreeArray;
    TreeArray=treedata;
    treedata=p_temp;
    size=num;
    delete[]treedata;
    treedata=NULL;
}
int CommonTree::find_same_ancestor(int Node1,int Node2,int array_num){
    int *array_Node1=newint[array_num];
    int *array_Node2=newint[array_num];
    if(array_Node1==NULL&&array_Node2==NULL) exit(1);
    int x=Node1,array_Node1_num=0;
    array_Node1[0]=x;
    while(x!=root){
        x=TreeArray[x];
        array_Node1_num++;
        array_Node1[array_Node1_num]=x;
    }
    x=Node2;
    int array_Node2_num=0;
    array_Node2[0]=x;
    while(x!=root){
        x=TreeArray[x];
        array_Node2_num++;
        array_Node2[array_Node2_num]=x;
    }
    QuickSort (array_Node2,0,array_Node2_num);
    int result=0;
    for(inti=0;i<=array_Node1_num;i++){
        result=FindSource(array_Node2,array_Node1[i],0,array_Node2_num);
        if(result!=-1) break;
    }
    delete[]array_Node1;
    delete[]array_Node2;
    return result;
}
inline int CommonTree::Size(){
    return size;
}
inline void CommonTree::getroot(int i){
    root=i;
}
void CommonTree::Print()
const{
    for(inti=1;i<size;i++) cout<<this->TreeArray[i]<<"";
    cout<<endl;
    cout<<root<<endl;
}
int main(){
    ifstreamin("input.txt");
    if( in.fail()){
        cout<<"inputerror!"<<endl;
        exit(1);
    }
    ofstreamout("output.txt");
    int NodeNum;
    in>>NodeNum;
    int *AncestorTree=newint[NodeNum+1];
    if(AncestorTree==NULL) exit(1);
    memset(AncestorTree,0,sizeof(int)*(NodeNum+1));
    int father=1;
    for(intj=0;j<NodeNum;j++){
        int lop;
        in>>lop;
        for(inti=0;i<lop;i++){
            int temp;
            in>>temp;
            AncestorTree[temp]=father;
        }
        father++;
    }
    for(j=1;j<=NodeNum;j++){
        if (AncestorTree[j]==0){
            AncestorTree[j]=j;
            break;
        }
    }
    int find_num;
    in>>find_num;
    int *result=newint[3*find_num];
    if(result==NULL) exit(1);
    for(inti=0;i<2*find_num;i++) in>>result[i];
    CommonTreemain_tree(10);
    main_tree.getdata(AncestorTree,NodeNum+1);
    main_tree.getroot(j);
    int displace=0;
    for(i=0;i<find_num;i++){
        result[2*find_num+i]=main_tree.find_same_ancestor(result[displace],result[displace+1],NodeNum);
        displace+=2;
    }
    displace=0;
    for(i=0;i<find_num;i++){
        out<<result[displace]<<""<<result[displace+1]<<""<<result[2*find_num+i];
        displace+=2;
        out<<endl;
    }
    delete[]result;
    return 0;
}

C++代碼實現：
#include<iostream>
#include<stdio.h>
#include<memory.h>
using namespace std;
#definemax_size 1010
int d[max_size],p[max_size][10];
int head[max_size];
int cnt;
structEdge{
    int v;
    int pre;
}eg[max_size];
//建樹的函數
void add(int x,int y){
    eg[cnt].v=y;
    eg[cnt].pre=head[x];
    head[x]=cnt++;
}
//dfs()初始整顆數，算出d[1-n],p[1-n][j];
void dfs(intk){
    if (head[k]==0) return;
    int m,x,i,j;
    for(i=head[k];i!=0;i=eg[i].pre){
        x=eg[i].v;
        p[x][0]=k;
        m=k;
        d[x]=d[k]+1;
        for(j=0;p[m][j]!=0;j++){
            p[x][j+1]=p[m][j];//利用公式p[x][j]=p[p[x][j-1]][j-1],這裏的m就是p[x][j-1];
            m=p[m][j];
        }
    dfs(x);
    }
}
int find_lca(int x,int y){
    int m,k;
    if (x==y) return x;
    if(d[x]<d[y]){m=x;x=y;y=m;}
    m=d[x]-d[y];
    k=0;
    while(m){//將x的深度調到和y的深度一樣
        if(m&1) x=p[x][k];
        m>>=1;
        k++;
    }
    if (x==y)return x;
    k=0;//向上調節，找最近公共祖先，算法的核心，相當於一個二分查找。
    while(x!=y){
        if (p[x][k]!=p[y][k]||p[x][k]==p[y][k]&&k==0){//如果p[x][k]還不相等，説明節點p[x][k]還在所求點的下面，所以繼續向上調節;如果相等了，並且就是他們父節點，則那個節點一定就是所求點。
            x=p[x][k];
            y=p[y][k];
            k++;
        }
    else k--;//如果p[x][k]=p[y][k],可以説明p[x][k]一定是x和y的共祖先，但不一定是最近的,所以向下找看還有沒有更近的公共祖先
    }
    return x;
}
int main(){
    int i,n,m,x,y;
    while(cin>>n>>m){
        memset(head,0,sizeof(head));
        memset(p,0,sizeof(p));
        memset(d,0,sizeof(d));
        cnt=1;
        for(i=2;i<=n;i++){
            scanf("%d",&x);
            add(x,i);
        }
        dfs(1);
        for(i=0;i<m;i++){
            scanf("%d%d",&x,&y);
            printf("%d/n",find_lca(x,y));
        }
    }
    return 0;
}