CodeStream

  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理 ::
  12 随笔 :: 0 文章 :: 6 评论 :: 0 Trackbacks

最近公共祖先(Least Common Ancestors) :

对于有根树T的两个结点u、v,最近公共祖先LCA(T,u,v)表示一个结点x,满足x是u、v的祖先且x的深度尽可能大。另一种理解方式是把T理解为一个无向无环图,而LCA(T,u,v)即u到v的最短路上深度最小的点。

解决LCA问题常用的有两种方法,一种是离线的Tarjan算法,时间复杂度为O(n+m),其中n为节点数(或边数,因为一个含有n个节点的树一定只有n-1条边),m为问题数。另外一种是在线的倍增法,时间复杂度为O(lg(m*n))。还有的就是最为朴树的算法,时间复杂度为
O(m*n)。

1、朴树的LCA算法:
   此种方法很好理解,首先建好一棵树,然后对于给定的问题:(x, y)求解(x,y)的最近公共祖先。可以在建树的过程中记录每个节点的深度,记录在数组d[1-n]中。 对于给定的节点(x,y),如果d[x] < d[y],那么交换x和y,保证d[x]   ≥ d[y],然后调整x,使d[x] = d[y]。这时x和y相当于处于同一高度。判断x和y的值,如果x=y,那么y就是x和y的最近公共祖先。
posted on 2011-03-25 18:34 CodeStream 阅读(2742) 评论(1)  编辑 收藏 引用 所属分类: acm_LCA

评论

# re: LCA (离线Tarjan && 在线倍增发)[未登录] 2015-10-22 21:01 john
good  回复  更多评论
  


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理