Найменший спільний предок вершин та в кореневому дереві — найвіддаленіша від кореня дерева вершина, яка лежить на обидвох шляхах від та до кореня дерева, тобто є предком обидвох вершин.
Алгоритми
- Алгоритм двійкового підйому. (Описано нижче в даній статті).
- Офлайновий алгоритм Тарджана
- Алгоритм Бендера — Фараха-Колтона.
Опис алгоритму методу двійкового підйому
Метод двійкового підйому — онлайн алгоритм вирішення задачі пошуку найменшого спільного предка. Він не використовує [en] і заснований на методі динамічного програмування.
Як і більшість online алгоритмів, цей метод спочатку робить підрахунок offline, а потім це використовує для відповіді на запити.
Підрахунок offline
Підрахунок offline полягає в тому, щоб порахувати функцію: — вершина, у яку ми прийдемо, пройшовши уверх ребер з вершини , при чому, якщо ми прийшли в корінь дерева, то там і залишаємося. Для цього спочатку запустимо обхід в глибину з кореня і для кожної вершини запишемо номер її батька та глибину вершини в підвішеному дереві . Якщо корінь — , то , тоді для функції є рекурентна формула :
Для того, щоб відповідати на запити, нам потрібні тільки ті значення , для яких , бо для великих значень дорівнюватиме значенню кореня.
Всього станів динаміки , де кількість вершин у дереві. Кожний стан рахується за , тому загальна складність .
Відповіді на запити
Відповідати на запити будемо за час . Спочатку помітимо, якщо вершина для деяких та то . Тому, якщо , то пройдемо від вершини на кроків уверх, це і буде нове значення , яке ми можемо порахувати за . Число ми можемо записати у двійковій системі числення як :
і для всіх пройти вверх послідовно із вершини у вершину .
Далі вважаємо, що .
Якщо , то відповідь на запит .
Інакше, якщо , то знайдемо такі вершини та , що та . Тоді відповіддю на запит буде .
Щоб знайти вершини та , спочатку ініціалізуємо та , та знаходитимемо таке максимальне , що . Тоді піднімемося вгору на кроків угору з обидвох вершин, та повторимо цю процедуру. Якщо такого знайти не можна, то знайдені вершини і є тими, які нам потрібно знайти, бо .
Оцінимо час роботи алгоритму.
Помітимо, що знайдені строго спадають, оскільки, по-перше, щоразу ми знаходимо максимальне значення , а по-друге, два рази поспіль одне й те саме значення отримати не можемо, бо і ми тоді б взяли , тому можна перебирати всього значень в порядку спадання. Отже, складність відповіді .
Псевдокод
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; (1973), On finding lowest common ancestors in trees, , с. 253—265, doi:10.1145/800125.804056.
- Наименьший общий предок. Нахождение за O (log N) (метод двоичного подъёма)
- Метод двоичного подъема
Див. також
Примітки
- . Архів оригіналу за 1 грудня 2018.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Najmenshij spilnij predok vershin u displaystyle u ta v displaystyle v v korenevomu derevi T displaystyle T najviddalenisha vid korenya dereva vershina yaka lezhit na obidvoh shlyahah vid u displaystyle u ta v displaystyle v do korenya dereva tobto ye predkom obidvoh vershin AlgoritmiAlgoritm dvijkovogo pidjomu Opisano nizhche v danij statti Oflajnovij algoritm Tardzhana Algoritm Bendera Faraha Koltona Opis algoritmu metodu dvijkovogo pidjomuMetod dvijkovogo pidjomu onlajn algoritm virishennya zadachi poshuku najmenshogo spilnogo predka Vin ne vikoristovuye en i zasnovanij na metodi dinamichnogo programuvannya Yak i bilshist online algoritmiv cej metod spochatku robit pidrahunok offline a potim ce vikoristovuye dlya vidpovidi na zapiti Pidrahunok offline Pidrahunok offline polyagaye v tomu shob porahuvati funkciyu d p v i displaystyle dp v i vershina u yaku mi prijdemo projshovshi uverh 2 i displaystyle 2 i reber z vershini v displaystyle v pri chomu yaksho mi prijshli v korin dereva to tam i zalishayemosya Dlya cogo spochatku zapustimo obhid v glibinu z korenya i dlya kozhnoyi vershini zapishemo nomer yiyi batka p v displaystyle p v ta glibinu vershini v pidvishenomu derevi d v displaystyle d v Yaksho korin v displaystyle v to p v v displaystyle p v v todi dlya funkciyi d p displaystyle dp ye rekurentna formula d p v i p v i 0 d p d p v i 1 i 1 i gt 0 displaystyle dp v i begin cases p v amp i 0 dp dp v i 1 i 1 amp i gt 0 end cases Dlya togo shob vidpovidati na zapiti nam potribni tilki ti znachennya d p v i displaystyle dp v i dlya yakih i log 2 n displaystyle i leqslant log 2 n bo dlya velikih znachen i d p v i displaystyle i dp v i dorivnyuvatime znachennyu korenya Vsogo staniv dinamiki O n log n displaystyle O n log n de n displaystyle n kilkist vershin u derevi Kozhnij stan rahuyetsya za O 1 displaystyle O 1 tomu zagalna skladnist O n log n displaystyle O n log n Vidpovidi na zapiti Vidpovidati na zapiti budemo za chas O log n displaystyle O log n Spochatku pomitimo yaksho vershina c L C A u v displaystyle c LCA u v dlya deyakih u displaystyle u ta v displaystyle v to d c min d u d v displaystyle d c leq min d u d v Tomu yaksho d u gt d v displaystyle d u gt d v to projdemo vid vershini u displaystyle u na d u d v displaystyle d u d v krokiv uverh ce i bude nove znachennya u displaystyle u yake mi mozhemo porahuvati za O log n displaystyle O log n Chislo d u d v displaystyle d u d v mi mozhemo zapisati u dvijkovij sistemi chislennya yak 2 i 1 2 i 2 2 i l displaystyle 2 i 1 2 i 2 2 i l i dlya vsih i j displaystyle i j projti vverh poslidovno iz vershini u displaystyle u u vershinu d p u i j displaystyle dp u i j Dali vvazhayemo sho d v d u displaystyle d v d u Yaksho v u displaystyle v u to vidpovid na zapit v displaystyle v Inakshe yaksho v u displaystyle v neq u to znajdemo taki vershini x displaystyle x ta y displaystyle y sho x y displaystyle x neq y ta p x p y displaystyle p x p y Todi vidpoviddyu na zapit bude p x displaystyle p x Shob znajti vershini x displaystyle x ta y displaystyle y spochatku inicializuyemo x v displaystyle x v ta y u displaystyle y u ta znahoditimemo take maksimalne k displaystyle k sho d p x k d p y k displaystyle dp x k neq dp y k Todi pidnimemosya vgoru na 2 k displaystyle 2 k krokiv ugoru z obidvoh vershin ta povtorimo cyu proceduru Yaksho takogo k displaystyle k znajti ne mozhna to znajdeni vershini i ye timi yaki nam potribno znajti bo p x d p x 0 d p y 0 p y displaystyle p x dp x 0 dp y 0 p y Ocinimo chas roboti algoritmu Pomitimo sho znajdeni k displaystyle k strogo spadayut oskilki po pershe shorazu mi znahodimo maksimalne znachennya k displaystyle k a po druge dva razi pospil odne j te same znachennya k displaystyle k otrimati ne mozhemo bo 2 k 2 k 2 k 1 displaystyle 2 k 2 k 2 k 1 i mi todi b vzyali k 1 displaystyle k 1 tomu mozhna perebirati vsogo O log n displaystyle O log n znachen k displaystyle k v poryadku spadannya Otzhe skladnist vidpovidi O log n displaystyle O log n Psevdokod 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 gt 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 Portal Programuvannya LiteraturaAho Alfred Hopcroft John 1973 On finding lowest common ancestors in trees s 253 265 doi 10 1145 800125 804056 Naimenshij obshij predok Nahozhdenie za O log N metod dvoichnogo podyoma Metod dvoichnogo podemaDiv takozhTeoriya grafiv Derevo teoriya grafiv Primitki Arhiv originalu za 1 grudnya 2018