Najniższy wspólny przodek (, 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) = 2i Jeśli taki wierzchołek nie istnieje, to p[i,v]=korzeń.

Rekurencyjnie można ją obliczyć ze wzoru

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[i]; }

void dfs(int v) { counter++; pre[v]=counter; for(auto i:V[v]){ if(!vis[i]) { P[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=true; dfs(1);

P=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 – gdzie to ilość wierzchołków w drzewie, a 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

Bibliografia https://oi.edu.pl/static/attachment/20110811/oi9.pdf.

Kategoria:Teoria grafów