Najniższy wspólny przodek

Najniższy wspólny przodek (ang. lowest common ancestor, LCA) – najniższym wspólnym przodkiem dwóch wierzchołków d oraz e w ukorzenionym drzewie T jest taki rodzic wierzchołków d oraz e, którego poziom w drzewie T jest największy.

Algorytm

Zdefiniujmy tablicę p:

p[i, v] – wierzchołek u leżący na ścieżce pomiędzy v i korzeniem, taki że odległość (u, v) = 2ⁱ Jeśli taki wierzchołek nie istnieje, to p[i,v]=korzeń.

Rekurencyjnie można ją obliczyć ze wzoru $p[i,v]=p[i-1,p[i-1,v]]$

Za pomocą tak utworzonej tablicy możemy analogicznie do techniki wyszukiwania binarnego odnaleźć LCA dwóch wierzchołków.

Przykładowy kod w języku c++ obliczający LCA na podstawie tablicy p.

#include <cstdio>
#include <vector>

#define MAX 1000005
#define LOGN 16

using namespace std;

vector<int> V[MAX];
int P[LOGN][MAX], pre[MAX], treeSize[MAX];
bool vis[MAX];

int n, from, to, counter=0;

bool children(int u, int v)
{
        return (pre[u]>=pre[v] && pre[u] < pre[v]+treeSize[v]);
}

int lca(int u, int v)
{
        if(children(u, v)) return v;
        if(children(v, u))return u;

        int i=u, j=LOGN-1;
        while(j>=0) {
                if(children(v, P[j][i]))
                        j--;
                else
                        i = P[j][i];
        }

        return P[0][i];
}

void dfs(int v)
{
        counter++;
        pre[v]=counter;
        for(auto i:V[v]){
                if(!vis[i]) {
                        P[0][i]=v;
                        vis[i]=true;
                        dfs(i);
                }
        }
        treeSize[v]=counter+1-pre[v];
}

int main()
{
        scanf("%d", &n);
        for(int i = 0; i < n-1; ++i) {
                scanf("%d %d", &from, &to);
                V[from].push_back(to);
                V[to].push_back(from);
        }
        for(int i = 0; i <= n; i++) {
                pre[i]=0;
                treeSize[i]=0;
                vis[i]=false;
        }
    for(int i = 0; i < LOGN; i++)
        for(int j = 0; j < MAX; j++)
            P[i][j]=0;

        vis[1]=true;
        dfs(1);

        P[0][1]=1;
        for(int i = 1; i < LOGN; i++)
                for(int j = 1; j < MAX; j++)
                        P[i][j]=P[i-1][P[i-1][j]];
        printf("%d\n",lca(1, 4));
        printf("%d\n",lca(3, 5));
        return 0;
}

Powyższy algorytm ma złożoność obliczeniową rzędu ${\mathcal {O}}(n\log(n)+k\log(n))$ – gdzie $n$ to ilość wierzchołków w drzewie, a $k$ to ilość zapytań o najniższego wspólnego przodka. Innym sposobem obliczania dla dwóch wierzchołków drzewa ich najniższego wspólnego przodka jest algorytm Tarjana. Istnieje także algorytm opublikowany w 2000 roku o złożoności obliczeniowej ${\mathcal {O}}(n+k).$

Bibliografia

• http://oi.edu.pl/static/attachment/20110811/oi9.pdf.