Найменший спільний предок

Найменший спільний предок вершин ${\displaystyle u}$ та ${\displaystyle v}$ в кореневому дереві ${\displaystyle T}$ — найвіддаленіша від кореня дерева вершина, яка лежить на обидвох шляхах від ${\displaystyle u}$ та ${\displaystyle v}$ до кореня дерева, тобто є предком обидвох вершин.

Алгоритми

• Алгоритм двійкового підйому. (Описано нижче в даній статті).
• Офлайновий алгоритм Тарджана
• Алгоритм Бендера — Фараха-Колтона[1].

Опис алгоритму методу двійкового підйому

Метод двійкового підйому — онлайн алгоритм вирішення задачі пошуку найменшого спільного предка. Він не використовує діапазон мінімального запиту^[en] і заснований на методі динамічного програмування.

Як і більшість online алгоритмів, цей метод спочатку робить підрахунок offline, а потім це використовує для відповіді на запити.

Підрахунок offline

Підрахунок offline полягає в тому, щоб порахувати функцію: ${\displaystyle dp[v][i]}$ — вершина, у яку ми прийдемо, пройшовши уверх ${\displaystyle 2^{i}}$ребер з вершини ${\displaystyle v}$, при чому, якщо ми прийшли в корінь дерева, то там і залишаємося. Для цього спочатку запустимо обхід в глибину з кореня і для кожної вершини запишемо номер її батька ${\displaystyle p[v]}$ та глибину вершини в підвішеному дереві ${\displaystyle d[v]}$. Якщо корінь — ${\displaystyle v}$, то ${\displaystyle p[v]=v}$, тоді для функції ${\displaystyle dp}$ є рекурентна формула :

${\displaystyle dp[v][i]={\begin{cases}p[v],&i=0,\\dp[dp[v][i-1]][i-1],&i>0.\end{cases}}}$

Для того, щоб відповідати на запити, нам потрібні тільки ті значення ${\displaystyle dp[v][i]}$, для яких ${\displaystyle i\leqslant \log _{2}n}$, бо для великих значень ${\displaystyle i\ \ dp[v][i]}$ дорівнюватиме значенню кореня.

Всього станів динаміки ${\displaystyle O(n\log n)}$, де ${\displaystyle n}$ кількість вершин у дереві. Кожний стан рахується за ${\displaystyle O(1)}$, тому загальна складність ${\displaystyle O(n\log n)}$.

Відповіді на запити

Відповідати на запити будемо за час ${\displaystyle O(\log n)}$. Спочатку помітимо, якщо вершина ${\displaystyle c=LCA(u,v)}$ для деяких ${\displaystyle u}$ та ${\displaystyle v}$ то ${\displaystyle d[c]\leq \min(d[u],d[v])}$. Тому, якщо ${\displaystyle d[u]>d[v]}$, то пройдемо від вершини ${\displaystyle u}$ на ${\displaystyle (d[u]-d[v])}$ кроків уверх, це і буде нове значення ${\displaystyle u}$, яке ми можемо порахувати за ${\displaystyle O(\log n)}$. Число ${\displaystyle (d[u]-d[v])}$ ми можемо записати у двійковій системі числення як :

${\displaystyle 2^{i_{1}}+2^{i_{2}}+...2^{i_{l}}}$ і для всіх ${\displaystyle i_{j}}$ пройти вверх послідовно із вершини ${\displaystyle u}$ у вершину ${\displaystyle dp[u][i_{j}]}$.

Далі вважаємо, що ${\displaystyle d[v]=d[u]}$.

Якщо ${\displaystyle v=u}$, то відповідь на запит ${\displaystyle v}$.

Інакше, якщо ${\displaystyle v\neq u}$, то знайдемо такі вершини ${\displaystyle x}$ та ${\displaystyle y}$, що ${\displaystyle x\neq y}$ та ${\displaystyle p[x]=p[y]}$. Тоді відповіддю на запит буде ${\displaystyle p[x]}$.

Щоб знайти вершини ${\displaystyle x}$ та ${\displaystyle y}$, спочатку ініціалізуємо ${\displaystyle x=v}$ та ${\displaystyle y=u}$, та знаходитимемо таке максимальне ${\displaystyle k}$, що ${\displaystyle dp[x][k]\neq dp[y][k]}$. Тоді піднімемося вгору на ${\displaystyle 2^{k}}$ кроків угору з обидвох вершин, та повторимо цю процедуру. Якщо такого ${\displaystyle k}$ знайти не можна, то знайдені вершини і є тими, які нам потрібно знайти, бо ${\displaystyle p[x]=dp[x][0]=dp[y][0]=p[y]}$.

Оцінимо час роботи алгоритму.

Помітимо, що знайдені ${\displaystyle k}$ строго спадають, оскільки, по-перше, щоразу ми знаходимо максимальне значення ${\displaystyle k}$, а по-друге, два рази поспіль одне й те саме значення ${\displaystyle k}$ отримати не можемо, бо ${\displaystyle 2^{k}+2^{k}=2^{k+1}}$ і ми тоді б взяли ${\displaystyle k+1}$, тому можна перебирати всього ${\displaystyle O(\log n)}$ значень ${\displaystyle k}$ в порядку спадання. Отже, складність відповіді ${\displaystyle O(\log n)}$.

Псевдокод

  function preprocess():
     int[] p = dfs(0)
     for i = 1 to n
        dp[i][0] = p[i]
     for j = 1 to log(n)
        for i = 1 to n
           dp[i][j] = dp[dp[i][j - 1]][j - 1]
  
  int lca(int v, int u):
     if d[v] > d[u]
        swap(v, u)
     for i = log(n) downto 0
        if d[u] - d[v] 
           u = dp[u][i]
     if v == u
        return v
     for i = log(n) downto 0
        if dp[v][i] != dp[u][i]
           v = dp[v][i]
           u = dp[u][i]
     return p[v]

Література

• Aho, Alfred; Hopcroft, John; Ullman, Jeffrey (1973), On finding lowest common ancestors in trees, Proc. 5th ACM Symp. Theory of Computing (STOC), с. 253—265, doi:10.1145/800125.804056.
• Наименьший общий предок. Нахождение за O (log N) (метод двоичного подъёма)
• Метод двоичного подъема

Див. також

• Теорія графів
• Дерево (теорія графів)

Примітки

1. Алгоритм Фарака-Колтона и Бендера. Архів оригіналу за 1 грудня 2018.