Прямолинейное дерево Штейнера: различия между версиями

На основе вышеприведенных рассуждений создан псевдокод алгоритма, представленный на рис. 3. На начальном этапе работы алгоритма для генерации остовного графа G для заданного множества точек используется алгоритм построения прямолинейного остовного графа Чжоу и др [17]. Затем к графу применяется алгоритм Крускала для генерации минимального остовного дерева. Структура данных на основе непересекающихся множеств [5] используется для слияния компонентов и проверки, принадлежат ли две точки к одному и тому же компоненту (первый цикл for). В процессе выполнения также генерируются бинарное дерево слияния и запросы по поводу наименьших общих предков для всех пар «точка-ребро». Здесь s, s1 и s2 представляют непересекающиеся множества, каждое из которых хранит корень компонента в бинарном дереве слияния. При каждом добавлении дуги (u, v) к T следует рассматривать любого соседа u или v, обозначим его за w, как кандидата на подключение к (u, v). Самое длиное ребро для этой пары будет наименьшим общим предком w и u либо w и v, в зависимости от того, какая точка оказывается в одном компоненте с точкой w. Добавление этого опроса производится при помощи процедуры lca_add_query. Соединение двух компонентов при помощи (u, v) также будет записано в бинарном дереве слияния при помощи процедуры lca_tree_edge. После генерации минимального остовного дерева у нас также имеются соответствующее бинарное дерево слияния и запросы по поводу наименьших общих предков. При помощи оффлайнового алгоритма Тарьяна для нахождения наименьших общих предков [5] (представленного процедурой lca_answer_queries) можно сгенерировать все самые длинные ребра для пар. При наличии информации о самом длинном ребре для каждой пары «точка-ребро» можно решить задачу подключения точки к ребру. После этого можно осуществить подключения точек к ребрам в порядке невозрастания прироста. Подключение может быть осуществлено только в случае, если ни ребро подключения, ни ребро удаления еще не были удалены.