注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

Hao的博客

I'm on my way……

 
 
 

日志

 
 
 
 

最近公共祖先LCA  

2013-04-09 13:38:48|  分类: Algorithm discov |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
一棵树上的两个节点u和v,它们的最近公共祖先(Least Common Ancestor)是指最靠近它们的祖先节点。如下图中有LCA(1,2)=3、LCA(1, 5)=4、LCA(9, 8)=6。
最近公共祖先LCA - chhaj5236 - Hao的博客
 
求解LCA(u, v)的一种方法是将其转换为两个单链表相交的问题,如求解LCA(9, 8)就是要找到9->7->6->4和8->6->4的第一个公共节点6:首先遍历两个单链表,得到两个单链表的长度(假设两个链表长度相差Δ),然后重新遍历两个链表,在指向较长链表的指针向右移动Δ后,再同时移动两个链表的指针,则两个指针第一个同时指向的节点即为所求节点。该方法对于Q组LCA查询的时间复杂度是O(Q*N),其中N为节点数。

除上述方法外,可以发现如果将DFS过程中经过的节点记录下来,如上图中DFS会首先访问4、然后3、1,之后回到3再2、再回到3、4以此类推(完整访问序列E={4, 3, 1, 3, 2, 3, 4, 5, 4, 6, 7, 9, 7, 6, 8, 6, 4}),则首次访问(即最早出现在访问序列中)u和v之间的访问序列必定仅限于u、v所在的最小子树,而这个子树的根节点即为LCA(u, v)。如首次访问节点9和8之间的访问序列为[9, 7, 6, 8],其中6为子树的根节点。可知LCA(9, 8)其实就是[9, 7, 6, 8]序列中离根节点最近(即深度最浅)的节点。所以可以定义另外一个和E一一对应的序列D,表示E中的节点在树中的深度(上图中D={0, 1, 2, 1, 2, 1, 0, 1, 0, 1, 2, 3, 2, 1, 2, 1, 0})。则LCA(u, v) = E[min(D, R[u], R[v])],其中R[u]和R[v]表示序列中首次访问节点u和v的位置,min(D, R[u], R[v])表示D中从R[u]到R[v]之间最小值的位置,即深度最浅的节点位置。DFS过程的部分代码如下:

struct Node{
int id; //节点ID
vector<Node*> children; //与该节点相联的其它节点
};

void DFS(Node *node, int depth){
if(!depth) { E.clear(); D.clear();}
E.push_back(node->id);
D.push_back(depth);
R[node->id] = E.size()-1; //记录首次访问的位置
visited[node->id]=true; //如果是无向边,就需要记录哪些节点已经访问过
for(vector<Node*>::iterator it=node->children.begin(); it!=node->children.end(); ++it){
if(visited[(*it)->id])continue;

DFS(*it, depth+1);
E.push_back(node->id);
D.push_back(depth);
}
}

当建立好E、D、R三个数组后,就只要计算D数组中从R[u]到R[v]之间最小值的位置。最小值计算最简单的方法就是遍历,时间复杂度O(N),Q次查询复杂度就是O(Q*N)。也可以对数组D进行一个O(NlogN)的预处理,后面的每个查询就只需要O(1)时间,这就涉及另外一个知识:RMQ(Range Minimum/Maximum Query)区间最值查询。RMQ的主要思想是将查询区间分成两个已知最小值(或最大值)的区间,从而得出查询区间的最小值(最大值),预处理的过程则使用dp(动态规划),该方法被称为ST(Sparse Table)。下面继续以最小值为例,假设F[i][j]表示从下标为i的项开始,长度为2^j的区间最小值,则有dp状态方程F[i][j] = min{ F[i][j-1], F[i+2^(j-1)][j-1] }。预处理后,若查询下标i到j之间的最小值(i<=j),则有RMQ(i, j) = min{ F[i][k], F[j-2^k+1][k] },其中k = log(j-i+1)/log2。由于上述LCA的实现需要返回的是最小值的位置,而非最小值,所以对RMQ的实现代码进行了细微的调整,如下所示:

void Init_RMQ(vector<int> D, int n){
int i, j;
for(i=0; i<n; ++i) F[i][0]=i; //F改为存储最小值在数组D中的下标
for(j=1; j<log((double)n)/log(2.0); ++j){
for(i=0; i<n-(1<<j)+1; ++i){

//根据D中的数值大小更新最小值下标
if(D[F[i][j-1]]<=D[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];
}
}
}
int RMQ(int s, int e){
if(s>e) swap(s,e);
int k = log(e-s+1.0)/log(2.0);

//根据D中数值大小,返回最小值位置
if(D[F[s][k]]<=D[F[e-(1<<k)+1][k]]) return F[s][k];
return F[e-(1<<k)+1][k];
}

上述方法即DFS+ST的思想,由于预处理过后,每个查询只需要O(1)的时间即可返回结果,所以该方法属于在线算法,用于实时地处理查询请求,时间复杂度为O(NlogN)。

现在来考虑第三种方法,同样是在DFS过程中,每个首次被访问的节点都自成一个集合,如果一个节点的所有子树都已被访问过,我们就标记这个节点为checked(如上图中红色的节点),并将根节点的父节点设置为这个子树的祖先(合并两个集合)。假设当前访问的节点是9,由于节点9没有任何子节点,所以标记节点9,这时候考虑所有以节点9开头的查询(9, x),如果后面的x属于已标记节点,则节点9和节点v的LCA必定是节点v所在集合的根节点4。上述方法被称为Tarjan算法,从上面的分析可知,该方法会重新组织查询序列,以达到更快的速度,所以该方法属于离线算法,必须在已知所有查询请求的前提下进行。Tarjan算法中涉及的集合操作则可以通过并查集实现。此外,如果上述过程中,x属于未标记节点则无法得出LCA,但是查询(x, 9)时,节点9必定属于已标记节点,所以对于每个查询(x, y),我们将(y, x)也加入到查询序列中。大致实现代码如下所示:

void Tarjan_DFS(Node *node, map<int, vector<int>> query){

ancestor[node->id] = node->id; //创建新的集合
visited[node->id]=true; //如果是无向边,就需要记录哪些节点已经访问过
for(vector<Node*>::iterator it=node->children.begin(); it!=node->children.end(); ++it){
if(visited[(*it)->id])continue;
Tarjan_DFS(*it);
ancestor[(*it)->id]=node->id;

}

checked[node->id]=true; //所有子树都遍历完,将当前节点设置为checked

//query内保存了以node->id开始的所有查询

for(vector<int>::iterator it=query[node->id].begin(); it!=query[node->id].end(); ++it){

//if checked[*it] answer corresponding query with getAncestor(*it);

}

}

参考资料:
[1] http://dongxicheng.org/structure/lca-rmq/
  评论这张
 
阅读(462)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017