最低公共祖先（升压图）

Question

是否有一个内置的方法在boost中查找树中两个或更多节点的最低共同祖先（这是一个boost :: graph实例）？

如果不是，我将不胜感激关于最佳方式的建议。在O（1）时间内（有O（n）预处理）有高效的算法来实现这一点，但它没有描述算法。

Answer 1

发现在Wikipedia算法：

function TarjanOLCA(u) 
MakeSet(u); 
u.ancestor := u; 
for each v in u.children do 
    TarjanOLCA(v); 
    Union(u,v); 
    Find(u).ancestor := u; 
u.colour := black; 
for each v such that {u,v} in P do 
    if v.colour == black 
     print "Tarjan's Least Common Ancestor of " + u + 
       " and " + v + " is " + Find(v).ancestor + "."; 

Answer 2

我发现下面的网站可以回答你的问题： http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor#Lowest%20Common%20Ancestor%20%28LCA%29

的基本思路是，以“最低共同祖先”的问题转化成一个又一个，“范围最小查询”，然后用一个Ø （N）+ O（1）方法来解决问题。我没有彻底研究它，但它看起来很好记录和值得看看。