Задача о наименьшем общем предке, решение методом двоичного подъема

  • 04 апр. 2012 г.
  • 432 Слова
Задача о наименьшем общем предке, решение методом двоичного подъема

Постановка задачи

Допустим, у нас есть дерево G, и мы хотим отвечать на запросы вида "найти наименьшего общего предкавершин V1 и V2", то есть, для каждой такой пары требуется найти самую нижнюю из всех вершин V, являющихся предками V1 и V2 одновременно. Очевидно, что наименьшим общим предком вершин V1 и V2 будет являться ихобщий предок, лежащий на кратчайшем пути из V1 в V2. В частности, если V1 является предком V2, то V1 является их наименьшим общим предком.

В англоязычной литературе эта задача встречается под названиемLCA problem - Least Common Ancestor или Lowest Common Ancestor.

Алгоритм

Предвычисления

Предвычисления выполняются с помощью обхода дерева G в глубину. Будем подниматься от каждой вершинына 1, 2, 4, 8 уровней и запоминать соответствующих подъему на это число уровней предков. Назовем соответствующий массив uplift, uplift[V][L], где V = 1..N, L = 0..log N, хранит 2^L-предка вершиныvertex. Эти вычисления требуют O(log N) операций для каждой из N вершин. Также для каждой вершины запомним времена входа в нее и выхода из нее при обходе в глубину - это нужно для того, чтобы за O(1)действий определять, является ли одна вершина предком другой.

Ответ на запрос

Пусть очередным запросом является пара вершин (V1, V2). Сначала проверим, не является ли одна вершина предком другой - в этомслучае она и будет ответом на запрос. Если ни для одной из вершин это не выполняется, то будем подниматься по предкам V1, пока не найдем самую близкую к корню дерева вершину, которая еще не являетсяпредком V2. Выполненный ранее предподсчет позволяет нам как бы разложить подъем на необходимое число уровней по степеням двойки. Ответом будет непосредственный предок найденной вершины.

Опишем этотпроцесс подробнее. Пусть L = log N. Пусть сначала I = L. Если uplift[V1][I] не является предком V2, то присваиваем V1 = uplift[V1][I], и уменьшаем I. Если же uplift[V1][I] является...
tracking img