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

Большую часть времени исполнения алгоритма занимают генерация остовного графа и сортировка ребер, требующие O(n log n) времени. Поскольку количество ребер в остовном графе составляет O(n), и алгоритм Крускала, и алгоритм Тарьяна для поиска наименьших общих предков занимают <math>O(n \alpha (n)) \;</math> времени, где <math>\alpha (n) \;</math> – обратная функция Аккермана, растущая исключительно медленно.

  <math>T = \empty</math>;

  Сгенерировать остовный граф G при помощи алгоритма RSG;

  '''for''' (каждой дуги <math>(u, v) \in G \;</math> по порядку неубывания длины) {

      s1 = find_set(u); s2 = find_set(v);

      '''if''' (s1!=s2){

        добавить (u, v) в дерево T;

        '''for''' (каждого соседа w точек u, v в G)

            '''if''' (s1 == find_set(w))

                  lca_add_query(w, u, (u, v));

            '''else''' lca_add_query(w, v, (u, v));

        lca_tree_edge((u, v), s1.edge);

        lca_tree_edge((u, v), s2.edge);

        s = union_set(s1, s2); s.edge = (u, v);

      }

  }

  сгенерировать пары «точка-ребро» на основе lca_answer_queries;

  '''for''' (каждой пары (p, (a, b), (c, d)) в порядке невозрастания положительного прироста)

      '''if''' (ребро (a, b), (c ,d) не было удалено из T) {

        подключить p к (a, b), добавив три ребра к T;

        удалить (a, b), (c, d) из T;

      }