Самый низкий общий предок (график повышения)

Question

Есть ли встроенный метод в boost, чтобы найти наименьшего общего предка двух или более узлов в дереве (который является экземпляром boost :: graph)?

Если нет, я был бы признателен за предложения о том, как лучше всего это сделать. Википедия утверждает, что существует эффективный алгоритм для достижения этого за O (1) время (с предварительной обработкой O (n)), но он не описывает алгоритмы.

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

Answer 2

Я нашел следующий сайт, который может ответить на ваш вопрос: http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor#Lowest%20Common%20Ancestor%20%28LCA%29

Основная идея состоит в том, чтобы преобразовать вопрос "Самый низкий общий предок" в другой, "Запрос минимального диапазона", а затем использовать подход O (N) + O (1) для решения проблемы. Я не изучил это полностью, но это кажется довольно хорошо задокументированным и стоит посмотреть.