Изменения

Алгоритм строит вспомогательное дерево <math>B = (V_B, E_B)</math>, являющееся подвешенным и полным ветвящимся (такое дерево, у вершин которого либо 0, либо 2 и более потомкапотомков, и в котором все листья находятся на одном уровне), для которого будет выполняться следующее: <math>w(Heavy(B, u, v)) = w(Heavy(T, u, v))</math> для любой пары вершин <math>u, v \in V_T</math>. Построение дерева <math>B</math> основано на [[Алгоритм Борувки|алгоритме Борувки]]. При инициализации алгоритма для каждой вершины <math>v \in T</math> создается лист <math>f(v)</math> в <math>B</math>. Пусть на некотором шаге алгоритма Борувки алгоритм объединяет множество деревьев <math>A</math> в одно дерево, обозначаемое <math>t</math>. При этом алгоритм выбирает некоторые рёбра с наименьшим весом, прилегающие к деревьям из множества <math>A</math>. Обозначим такое ребро для некоторого дерева <math>a \in A</math> как <math>adj(a)</math>. Тогда алгоритм создает новую вершину <math>f(t)</math> в <math>V_B</math> и добавляет новые рёбра в <math>E_B</math> как <math>\{\{f(t), f(a)\} | a \in A\}</math>. Каждому ребру <math>\{f(t), f(a)\}</math> присваивается вес выбранного алгоритмом Борувки ребра, т.е. <math>w(\{f(t), f(a)\}) := w(adj(a))</math>.

Предположим, что <math>s</math> {{---}} вершина-потомок <math>v</math>, и известно множество <math>A(s) = \{A(s, l_1), A(s, l_1l_2),\dots\}</math>. Рассмотрим случай одного листа <math>l_i</math>. Очевидно, что все пути из корня в <math>l_i</math>, проходящие через <math>s</math>, также проходят через <math>v</math>. Так как ребро <math>\{v, s\}</math> связывает <math>v</math> и <math>s</math>, получим, что <math>A(v, l_i) = \arg\max\{w(A(s, l_i)), w(\{v, s\})\}</math>. Следовательно, для того, чтобы найти <math>A(v)</math>, достаточно сравнить веса рёбер из <math>A(s)</math> с весом ребра <math>\{v, s\}</math>. Данное сравнение можно эффективно выполнить с помощью двоичного поиска. Итоговое множество <math>A(v)</math> получается путем объединением множеств рёбер, полученных для каждого потомка.

Рёбра в дереве получают тег, который формируется следующим образом. Рассмотрим ребро <math>e = \{u, v\}</math>, где <math>v</math> находится дальше от корня. Пусть <math>d(v)</math> обозначает расстояние от вершины <math>v</math> до корня, а <math>i(v)</math> {{---}} номер младшей единицы в номере вершины <math>v</math>. Тогда тег ребра <math>e</math> {{---}} строка размера <math>\lceil\lg\lg |V_T|\rceil</math>, записанная как последовательность <math><d(v), i(v)></math>. В оригинальной работе было показано, что имея тег ребра и номер вершины, можно обнаружить ребро в графе за константное время.

Для каждой вершины <math>v</math> создается вектор длины <math>\lceil\lg|V_T|\rceil</math>, обозначаемый как <math>LCA(v)</math>, чей бит с номером i равен 1тогда, когда существует путь из листа в поддереве с корнем <math>v</math> в лист в другом поддереве, наивысшая по уровню вершина которого (иначе говоря, наименьший общий предок двух листьев) находится на расстоянии <math>i</math> от <math>v</math>.