最近公共祖先（boost图）

Question

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

如果没有，我希望能提供关于最佳方法的建议。 维基百科声称 有有效的算法可以在O（1）时间内实现这一点（具有O（n）预处理），但它没有描述算法。

- Amir Rachum

---

是的，我的意思是在一棵树中。抱歉造成混淆。 - Amir Rachum

Answer 1

在 维基百科 上找到了这个算法：

 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 + ".";

- Amir Rachum

Answer 2

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

基本思路是将“最近公共祖先”问题转化为另一个问题，“区间最小查询”，然后使用O(N)+O(1)方法解决问题。虽然我没有仔细研究过，但它似乎有很好的文档记录，值得一看。

- Benoît