Ancêtre commun le plus bas (graphique boost)

Question

Existe-t-il une méthode intégrée dans boost pour trouver l'ancêtre commun le plus bas de deux nœuds ou plus dans un arbre (qui est une instance boost :: graph)?

Sinon, j'apprécierais des suggestions sur la meilleure façon de le faire. Wikipedia claims il existe un algorithme efficace pour y parvenir en O (1) temps (avec pré-traitement O (n)), mais il ne décrit pas les algorithmes.

Answer 1

trouvé l'algorithme 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

J'ai trouvé le site suivant qui peut répondre à votre question: http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor#Lowest%20Common%20Ancestor%20%28LCA%29

L'idée de base est de convertir le « Lowest Common Ancestor » question dans un autre, « Plage de requête minimale », puis d'utiliser un O (N) + O (1) approche pour résoudre le problème. Je n'ai pas examiné à fond mais il semble assez bien documenté et mérite d'y jeter un coup d'oeil.