基本介紹
- 中文名：最近公共祖先
- 外文名：Lowest Common Ancestors
- 簡稱：LCA
- 算法：離線算法，倍增法
算法簡介,算法,算法實例,
算法簡介
另一種理解方式是把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]=truethen回答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 1010int 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;}