Introduction

Le plus proche ancêtre commun (PPAC), noté lca(a, b), désigne le nœud le plus profond qui est ancêtre à la fois de a et b dans un arbre enraciné. Plusieurs algorithmes permettent de résoudre ce problème, chacun offrant un compromis différent entre le prétraitement, la complexité par requête et le mode de fonctionnement (en ligne ou hors ligne).

Algorithme par sauts binaires (Binary Lifting)

C'est la technique la plus répandue pour calculer le PPAC en ligne. Chaque requête s'exécute en O(log n), après un prétraitement en O(n log n).

Principe fondamental

On maintient deux tableaux :

• prof[i] : la profondeur du nœud i (la racine est à profondeur 0).
• anc[i][k] : le nœud atteint en remontant de 2k niveaux depuis i.

Soient deux nœuds a et b tels que prof[a] ≥ prof[b]. L'idée est la suivante :

1. On remonte a jusqu'à ce qu'il soit au même niveau que b, en décomposant la différence de profondeur en binaire.
2. Ensuite, on remonte simultanément a et b de manière synchronisée, toujours par sauts de puissances de deux, jusqu'à ce que leurs ancêtres directs coïncident. Le nœud où cette coïncidence se produit est le PPAC.

Le tableau anc se construit par récurrence : pour aller de i sur 2k niveaux, on fait d'abord un saut de 2k-1, puis un autre depuis le nœud intermédiaire. La formule est anc[i][k] = anc[anc[i][k-1]][k-1]. Les valeurs initiales (anc[i][0]) correspondent au parent direct de chaque nœud.

On choisit une valeur maximale pour k supérieure ou égale à ⌊log₂ n⌋. Lorsqu'un saut dépasse la racine, on associe la valeur 0 (nœud fictif), ce qui simplifie les conditions aux limites.

Étapes détaillées

Prétraitement

On parcourt l'arbre (DFS ou BFS) et on remplit les tableaux :

1. Pour chaque nœud u avec parent p, on pose prof[u] = prof[p] + 1 et anc[u][0] = p.
2. On calcule ensuite anc[u][i] pour i allant de 1 à K (où K = ⌊log₂ n⌋) grâce à la relation de récurrence.
3. On poursuit le parcours sur les enfants de u.

Requête PPAC

1. Égaliser les profondeurs : en partant du bit le plus significatif, on remonte le nœud le plus profond par sauts successifs jusqu'à atteindre la profondeur de l'autre.
2. Si les deux nœuds coïncident à ce stade, on a trouvé le résultat.
3. Sinon, en parcourant les bits de K à 0, on remonte simultanément les deux nœuds tant que leurs ancêtres à ce niveau sont distincts.
4. À la fin de cette boucle, le parent de l'un des deux nœuds (par exemple anc[a][0]) est le PPAC recherché.

Implémentation

Prétraitement par DFS

void preparer(int noeud, int parent)
{
    prof[noeud] = prof[parent] + 1;
    anc[noeud][0] = parent;
    for (int p = 1; p <= K; p++)
        anc[noeud][p] = anc[anc[noeud][p - 1]][p - 1];

    for (int idx = tete[noeud]; idx != -1; idx = suivant[idx])
    {
        int voisin = dest[idx];
        if (voisin == parent) continue;
        preparer(voisin, noeud);
    }
}

Prétraitement par BFS

void preparerBFS(int racine)
{
    memset(prof, 0x3f, sizeof prof);
    prof[0] = 0;
    prof[racine] = 1;
    int debut = 0, fin = 0;
    file[fin] = racine;

    while (debut <= fin)
    {
        int courant = file[debut++];
        for (int idx = tete[courant]; idx != -1; idx = suivant[idx])
        {
            int voisin = dest[idx];
            if (prof[voisin] > prof[courant] + 1)
            {
                prof[voisin] = prof[courant] + 1;
                anc[voisin][0] = courant;
                file[++fin] = voisin;
                for (int p = 1; p <= K; p++)
                    anc[voisin][p] = anc[anc[voisin][p - 1]][p - 1];
            }
        }
    }
}

Calcul du PPAC

int ppac(int x, int y)
{
    if (prof[x] < prof[y]) swap(x, y);

    for (int p = K; p >= 0; p--)
        if (prof[anc[x][p]] >= prof[y])
            x = anc[x][p];

    if (x == y) return x;

    for (int p = K; p >= 0; p--)
        if (anc[x][p] != anc[y][p])
        {
            x = anc[x][p];
            y = anc[y][p];
        }

    return anc[x][0];
}

Extension : maximum sur le chemin

On peut enrichir le prétraitement pour calculer simultanément la valeur maximale sur le chemin entre deux nœuds. On utilise un tableau valeur_max[i][k] qui stocke le maximum rencontré en remontant de 2k niveaux depuis i. La récurrence devient :

valeur_max[i][p] = max(valeur_max[i][p - 1], valeur_max[anc[i][p - 1]][p - 1]);

Cette variante se combine naturelllement avec le calcul du PPAC et reste en O(log n) par requête.

Méthode de marquage ascendant

Approche naïve consistant à remonter depuis a en marquant chaque nœud visité, puis à remonter depuis b jusqu'à trouver le premier nœud marqué. Ce nœud est le PPAC. La complexité dans le pire cas est O(n) par requête, ce qui la rend peu pratique pour un usage dynamique. Elle sert surtout de base conceptuelle pour comprendre l'algorithme de Tarjan.

Algorithme de Tarjan (hors ligne)

Tarjan propose une approche hors ligne en O(n + m), où n est le nombre de nœuds et m le nombre de requêtes. L'idée repose sur une combinaison d'un parcours DFS et d'une structure union-find.

Principe

Lors du DFS, les nœuds se répartissent en trois catégories :

• En cours de visite (fonction DFS active) : ils forment un chemin depuis la racine jusqu'au nœud courant.
• Traité (fonction DFS terminée) : le sous-arbre entier a été exploré.
• Pas encore visité.

Chaque nœud traité est fusionné via union-find avec son parent. Pour une requête (u, v) où v est déjà traité lors de la visite de u, le représentant de v dans l'union-find correspond au plus proche ancêtre commun de u et v.

Implémentation

void tarjan(int noeud)
{
    marque[noeud] = 1;
    for (int idx = tete[noeud]; idx != -1; idx = suivant[idx])
    {
        int voisin = dest[idx];
        if (marque[voisin]) continue;
        tarjan(voisin);
        unite(voisin, noeud);
    }
    for (auto &req : requetes[noeud])
    {
        int cible = req.cible, identifiant = req.id;
        if (marque[cible] == 2)
            reponses[identifiant] = trouver(cible);
    }
    marque[noeud] = 2;
}

Les requêtes sont pré-chargées dans des listes d'adjacence par nœud. Chaque réponse est calculée en temps quasi-constant grâce à l'union-find avec compression de chemin et union par rang.