Минимальные остовные деревья

Представления

В этой главе мы займемся взвешенными неориентированными графами — самой естественной средой для задачи MST. Наверно, проще всего начать с расширения базовых представлений графа из : в представлении матрицей смежности вместо логических значений могут быть проставлены веса ребер; в представлении списками смежности в элементы списка, представляющие ребра, можно добавить поле веса. Этот классический подход привлекает своей простотой, но мы будем пользоваться другим методом, который не намного сложнее, зато позволит использовать наши программы в более общих условиях. Сравнительные характеристики производительности этих подходов будут проведены ниже в данной главе.

Чтобы рассмотреть все вопросы, возникающие при переходе от графов, где нас интересует только наличие или отсутствие ребер, к графам, в которых нам важна информация, связанная с ребрами, удобно представить ситуации, где вершины и ребра представляют собой объекты неизвестной сложности. Возможно, они являются какой-то частью крупной базы данных клиентов, которая создана и используется другим приложением. Например, бывает нужно рассматривать улицы, дороги и автострады в географической базе данных как абстрактные ребра, где веса представляют их длины. Но записи базы данных могут содержать и другую информацию — например, название дороги и ее тип, подробное описание ее физических свойств, интенсивность движения и т.п. Клиентская программа может выбрать нужную информацию, построить граф, обработать его, а затем интерпретировать полученные результаты в контексте базы данных — но это может оказаться сложным и трудоемким процессом. В частности, для этого нужна (по меньшей мере) копия графа.

В клиентских программах удобнее определить тип данных EDGE, а в реализациях — работать с указателями на ребра. В программе 20.1 описаны абстрактные типы данных EDGE, GRAPH и итератора, которые нужны для этого подхода. Клиенты легко могут удовлетворить минимальные требования типа данных EDGE, позволяя при этом определять типы данных для использования в контекстах других приложений. Наши реализации могут работать с указателями на ребра и использовать интерфейс для извлечения необходимой им информации из объектов EDGE независимо от их представления. Пример клиентской программы, использующей этот интерфейс, приведен в программе 20.2.

При тестировании алгоритмов и в базовых приложениях мы будем использовать класс EDGE (ребро), содержащий два приватных члена данных типа int и один типа double, которые инициализируются аргументами конструктора и возвращаются, соответственно, функциями-членами v(), w() и wt() (см. упражнение 20.8). Для единообразия в этой главе и в главе 21 мы будем представлять веса ребер типом данных double. В наших примерах в качестве весов ребер будут использоваться вещественные числа от 0 до 1. Это решение не противоречит различным вариантам, которые могут встретиться в приложениях, поскольку всегда можно явно или неявно масштабировать веса, чтобы они соответствовали этой модели (см. упражнения 20.1 и 20.10). Например, если весами являются положительные целые числа, меньшие известного максимального значения, то поделив значения весов на это максимальное значение, мы преобразуем их в вещественные числа из диапазона от 0 до 1.

При желании можно было бы разработать более общий интерфейс АТД и использовать для весов ребер любой тип данных, который поддерживает операции сложения, вычитания и сравнения, поскольку мы не только накапливаем суммы весов и принимаем решения в зависимости от их значений. В алгоритмах, которые будут рассмотрены в , понадобятся сравнения линейных комбинаций весов ребер, а время выполнения некоторых алгоритмов зависит от арифметических свойств весов, поэтому мы перейдем на целочисленные веса, чтобы упростить анализ алгоритмов.

Программы 20.2 и 20.3 реализуют АТД взвешенного графа из программы 20.1, представленного матрицей смежности. Как и раньше, для вставки ребра в неориентированный граф нужно занести указатели на него в двух местах матрицы — по одному для каждого направления ребра. Как обычно для алгоритмов, работающих с представлением неориентированных графов в виде матрицы смежности, их время выполнения пропорционально V² (на инициализацию матрицы) или выше.

Программа 20.1. Интерфейс АТД для графов со взвешенными ребрами

Этот код определяет интерфейс для графов с весами и другой информацией, связанной с ребрами. Он содержит интерфейс АТД ребра EDGE и шаблонный интерфейс графа GRAPH, которые можно использовать в любой реализации интерфейса EDGE. Реализации GRAPH работают с указателями на ребра (они берутся в клиентах из функции insert), а не самими ребрами. Класс ребер содержит также функции-члены, которые предоставляют информацию об ориентации ребра: либо e->from(v) истинно, e->v() равно v, а e->other(v) содержит e->w(); либо e->from(v) ложно, e->w() равно v, а e->other(v) содержит e->v().

  class EDGE {
    public:
      EDGE(int, int, double);
      int v() const;
      int w( ) const;
      double wt() const;
      bool from(int) const;
      int other(int) const;
  };
  template <class Edge>
  class GRAPH {
    public:
      GRAPH(int, bool);
      ~GRAPH();
      int V() const;
      int E() const;
      bool directed() const;
      int insert(Edge *);
      int remove(Edge *);
      Edge *edge(int, int);
      class adjIterator {
        public:
          adjIterator(const GRAPH , int);
          Edge *beg();
          Edge *nxt();
          bool end();
       };
  };
      

Программа 20.2. Пример клиентской функции обработки графа

Данная функция демонстрирует применение интерфейса взвешенного графа из программы 20.1. При любой реализации этого интерфейса функция edges возвращает вектор, содержащий указатели на все ребра графа. Как и в главах 17—19, обычно функции итератора используются только так, как показано здесь.

  template <class Graph, class Edge>
  vector <Edge *> edges(const Graph G)
    { int E = 0;
      vector <Edge *> a(G.E());
      for (int v = 0; v < G.V(); v++)
        { typename Graph::adjIterator A(G, v);
          for (Edge* e = A.beg(); !A.end(); e = A.nxt())
            if (e->from(v)) a[E++] = e;
        }
      return a;
    }
      

Проверка на существование ребра v-w при таком представлении сводится к проверке, является ли пустым указатель на пересечении строки v и столбца w. Иногда можно избежать таких проверок с помощью сигнальных значений для весов, однако в наших реализациях сигнальные значения использоваться не будут.

Программа 20.5 содержит детали реализации АТД взвешенного графа с указателями на ребра в представлении списками смежности. Вектор, индексированный именами вершин, ставит в соответствие каждой вершине связный список инцидентных ей ребер. Каждый узел списка содержит указатель на ребро. Как и в случае матрицы смежности, при желании можно сэкономить память, храня в узлах списков конечные вершины и веса (с неявным указанием исходной вершины), но за счет усложнения итератора (см. упражнения 20.11 и 20.14).

Программа 20.3. Класс взвешенного графа (матрица смежности)

Для насыщенных взвешенных графов мы используем матрицу указателей на данные типа Edge с указателем на ребро v-u в строке v и столбце w. Для неориентированных графов заносится еще один указатель на ребро — в строке w и столбце v. Пустой указатель означает отсутствие ребра; для удаления ребра функция remove() удаляет указатель на него. Данная реализация не выполняет проверку на наличие параллельных ребер, хотя клиенты могут воспользоваться для этого функцией edge.

  template <class Edge>
  class DenseGRAPH
    { int Vcnt, Ecnt; bool digraph;
      vector <vector <Edge *> > adj;
    public:
      DenseGRAPH(int V, bool digraph = false) :
        adj(V), Vcnt(V), Ecnt(0), digraph(digraph)
        { for (int i = 0; i < V; i++)
            adj[i].assign(V, 0);
        }
      int V() const { return Vcnt; }
      int E() const { return Ecnt; }
      bool directed() const { return digraph; }
      void insert(Edge *e)
        { int v = e->v(), w = e->w ();
          if (adj[v][w] == 0) Ecnt++;
          adj [ v] [ w] = e;
          if (!digraph) adj[w][v] = e;
        }
      void remove(Edge *e)
        { int v = e->v(), w = e->w ();
          if (adj[v][w] != 0) Ecnt —;
          adj[v][w] = 0;
          if (!digraph) adj[w][v] = 0;
        }
      Edge* edge(int v, int w) const
        { return adj[v][w]; }
      class adjlterator;
      friend class adjlterator;
    };
      

Программа 20.4. Класс итератора для представления матрицей смежности

Этот код, возвращающий указатели на ребра, является простой адаптацией программы 17.8.

  template <class Edge>
  class DenseGRAPH<Edge>::adjIterator
    { const DenseGRAPH<Edge> G;
      int i, v;
    public:
      adjIterator(const DenseGRAPH<Edge> G, int v) :
        G(G), v(v), i(0) { }
      Edge *beg()
        { i = -1; return nxt(); }
      Edge *nxt()
        { for (i++; i < G.V(); i++)
            if (G.edge(v, i)) return G.adj[v][i];
          return 0;
        }
      bool end() const
        { return i >= G.V(); }
    } ;
      

Программа 20.5. Класс взвешенного графа (списки смежности)

Данная реализация интерфейса из программы 20.1 основана на представлении графа в виде списков смежности и поэтому удобна для разреженных взвешенных графов. Как и в случае невзвешенных графов, каждое ребро представляется узлом списка, но здесь каждый узел содержит указатель на соответствующее ребро, а не просто на конечную вершину. Класс итератора представляет собой непосредственную адаптацию программы 17.10 (см. упражнение 20.13).

  template <class Edge>
  class SparseMultiGRAPH
    { int Vcnt, Ecnt; bool digraph;
      struct node
        { Edge* e; node* next;
          node(Edge* e, node* next): e(e), next(next) {}
        };
      typedef node* link;
      vector <link> adj;
    public:
      SparseMultiGRAPH(int V, bool digraph = false) :
        adj(V), Vcnt(V), Ecnt(0), digraph(digraph) { }
      int V() const { return Vcnt; }
      int E() const { return Ecnt; }
      bool directed() const { return digraph; }
      void insert(Edge *e)
        { adj[e->v()] = new node(e, adj[e->v()]);
          if (!digraph)
            adj[e->w()] = new node(e, adj[e->w()]);
          Ecnt++;
        }
      class adjIterator;
      friend class adjIterator;
    };
      

На этом этапе полезно сравнить эти представления с простыми представлениями, о которых шла речь в начале этого раздела (см. упражнения 20.11 и 20.12). Если строить граф с нуля, то, конечно, использование указателей потребовало бы большего объема памяти. Память нужна не только для размещения указателей, но и для индексов (имен вершин), которые в простых реализациях представлены неявно. Чтобы использовать указатели на ребра в представлении матрицей смежности, требуется дополнительный объем памяти для размещения V² указателей на ребра и E пар индексов. Аналогично, чтобы использовать указатели на ребра в представлении списками смежности, требуется дополнительный объем памяти для размещения E указателей на ребра и E индексов.

Однако использование указателей на ребра зачастую позволяет получить более быстрый код, поскольку скомпилированный код клиентской программы получает непосредственный доступ к весу через один указатель — в отличие от простой реализации, где сначала создается элемент типа Edge (ребро), а затем выполняется обращение к его полям. Если память критична, то применение минимальных представлений (и, возможно, оптимизация итераторов для экономии времени) может быть разумным вариантом, но в остальных случаях гибкость, которую дает применение указателей, стоит дополнительных затрат памяти.

Однако на всех рисунках будут применяться простые представления, чтобы не загромождать их. То есть мы будем показывать не матрицы указателей на структуры ребер (пара целых чисел и вес), а просто матрицы весов, и вместо узлов списков с указателями на структуры ребер мы будем показывать узлы, содержащие конечные вершины ребер. Представления нашего демонстрационного графа в виде матрицы смежности и списков смежности приведены на рис 20.3.

Что касается реализаций неориентированных графов, то ни в одной из реализаций не выполняется проверка на наличие параллельных ребер.

Два стандартных представления взвешенных неориентированных графов содержат веса в каждом представлении ребра. Здесь показаны представления графа, изображенного на

В зависимости от приложения можно изменить представление матрицей смежности так, чтобы сохранять параллельные ребра с наименьшим или наибольшим весом, либо сливать параллельные ребра в единое ребро с весом, равным сумме весов параллельных ребер. В представлении списками смежности параллельные ребра могут присутствовать в структуре данных, хотя можно построить более совершенные структуры данных, позволяющие отказаться от них с помощью одного из правил, описанных для матриц смежности (см. упражнение 17.49).

А как представить само MST-дерево? MST-дерево графа G — это подграф графа G, который сам по себе является деревом, поэтому возможны различные варианты, основными из которых являются:

На рис 20.4 показаны эти варианты для MST-дерева с рис 20.1. Еще один вариант — определить и использовать АТД для деревьев.

Одно и то же дерево может иметь различные представления в любой из указанных выше схем. В каком порядке следует хранить ребра в представлении списком ребер? Какой узел выбрать в качестве корня в представлении родительскими ссылками (см. упражнение 20.21)? Вообще-то конкретное представление MST-дерева, которое получается при выполнении алгоритма MST, зависит только от используемого алгоритма и не отражает никаких важных свойств MST-дерева.

Здесь показаны различные представления MST-дерева с рис 20.1. Наиболее простым является список его ребер в произвольном порядке (слева). MST-дерево — это разреженный граф, и его можно представить списками смежности (в центре). Наиболее компактным является представление родительскими ссылками: одна из вершин выбирается в качестве корня, и используются два вектора, индексированные именами вершин: один содержит родительский узел для каждой вершины дерева, а второй — вес ребра, ведущего из данной вершины к ее родителю (справа). Ориентация дерева (выбор корневой вершины) произвольна и не является свойством MST-дерева. Любое из этих представлений можно преобразовать в любое другое за линейное время.

Выбор представления MST-дерева не оказывает заметного влияния на алгоритм, поскольку каждое из этих представлений можно легко преобразовать в любое другое. Чтобы преобразовать представление MST-дерева в виде графа в вектор ребер, можно воспользоваться функцией GRAPHedges из программы 20.2. Чтобы преобразовать представление в виде родительских ссылок, хранящихся в векторе st (с весами в отдельном векторе wt), в вектор указателей на ребра mst, можно воспользоваться циклом

  for (k = 1; k < G.V(); k++)
    mst[k] = new EDGE (k, st[k], wt[k]);
      

Здесь приведен типичный случай, когда в качестве корня MST-дерева выбирается вершина 0, а фиктивное ребро 0-0 не помещается в список ребер MST-дерева.

Оба эти преобразования тривиальны, но как преобразовать представление в виде вектора указателей на ребра в представление родительскими ссылками? В нашем распоряжении имеются средства, позволяющие легко решить и эту задачу: можно преобразовать представление графа с помощью цикла вроде вышеприведенного (только с вызовом функции insert для каждого ребра), а затем выполнить поиск в глубину из любой вершины, чтобы вычислить за линейное время представление дерева DFS родительскими ссылками.

В общем, хотя представление MST-дерева можно выбирать как удобно, мы оформим все наши алгоритмы в класс обработки графов MST, который вычисляет приватный вектор mst указателей на ребра. В зависимости от потребностей приложений для данного класса можно реализовать функции-члены, которые возвращают этот вектор или предоставляют клиентским программам другую информацию об MST-дереве, но мы не будем вдаваться в дальнейшие детали этого интерфейса. Отметим лишь наличие функции-члена show, которая вызывает аналогичную функцию для каждого ребра MST-дерева (см. упражнение 20.8).

Упражнения

20.8. Напишите класс WeightedEdge (взвешенное ребро), который реализует интерфейс EDGE из программы 20.1 и содержит функцию-член show, которая выводит ребра и их веса в формате, используемом в рисунках этой главы.

20.9. Реализуйте класс io для взвешенных графов, содержащий функции-члены show, scan и scanEZ (см. программу 17.4).

20.10. Постройте АТД графа, который использует целочисленные веса, отслеживает минимальный и максимальный вес в графе и содержит функцию АТД, которая всегда возвращает веса, представленные числами из диапазона от 0 до 1.

20.11. Приведите интерфейс наподобие программы 20.1 для работы клиентов и реализаций с переменными типа Edge (а не с указателями на них).

20.12. Разработайте реализацию интерфейса из упражнения 20.11, в которой используется минимальное представление матрицей весов, а функция итератора nxt использует информацию, неявно содержащуюся в индексах строк и столбцов, для создания переменных типа Edge и возврата его значения клиентской программе.

20.13. Реализуйте класс итератора для использования в программе 20.5 (см. программу 20.4).

20.14. Разработайте реализацию интерфейса из упражнения 20.11, в которой используется минимальное представление списками смежности, узлы списка содержат вес и конечную вершину (но не начальную вершину), а функция итератора nxt использует неявную информацию для создания переменных типа Edge и возврата значений клиентской программе.

20.15. Внесите в генератор разреженных случайных графов из программы 17.12 возможность присваивания ребрам случайных весов (от 0 до 1).

20.16. Внесите в генератор насыщенных случайных графов из программы 17.13 возможность присваивания ребрам случайных весов (от 0 до 1).

20.17. Напишите программу, которая генерирует случайные взвешенные графы, соединяя вершины решетки размером , но для неориентированных графов) и присваивая каждому ребру случайный вес (от 0 до 1).

20.18. Напишите программу генерации случайных полных графов с нормально распределенными весами ребер.

20.19. Напишите программу, которая генерирует V случайных точек на плоскости, затем строит взвешенный граф, соединяя каждую пару точек, расположенных друг от друга на расстоянии не более d, ребрами с весом, равным этому расстоянию (см. упражнение 17.74). Определите, каким должно быть d, чтобы ожидаемое количество ребер было равно E.

20.20. Найдите в интернете крупный взвешенный граф — возможно, карту с расстояниями, список телефонных переговоров с их стоимостями или расписание авиарейсов с ценами на билеты.

20.21. Составьте матрицу размером 8 х 8, содержащую представления родительскими ссылками для всех ориентаций MST-дерева для графа с рис 20.1. Поместите в i-ю строку этой матрицы представление родительскими ссылками для дерева с корнем в вершине i.

20.22. Предположим, что конструктор класса MST генерирует представление MST-дерева в виде вектора указателей на ребра с элементами от mst[1] до mst[V]. Добавьте функцию-член ST (например, как в программе 18.3) — такую, что ST(v) возвращает в клиентскую программу родителя вершины v в этом дереве (или саму v, если это корень).

20.23. Для условий из упражнения 20.22 напишите функцию-член, которая возвращает суммарный вес MST-дерева.

20.24. Предположим, что конструктор класса MST генерирует представление MST-дерева в виде родительских ссылок в векторе st. Напишите код, который необходимо добавить в конструктор для вычисления представления этого дерева в виде вектора указателей на ребра в элементах приватного вектора mst с индексами 1, ..., V.

20.25. Определите класс TREE (дерево). Затем для условий из упражнения 20.22 напишите функцию-член, которая возвращает результат типа TREE.

Основные принципы алгоритмов построения MST -дерева

Построение MST-дерева — одна из наиболее изученных задач среди описанных в этой книге. Основные принципы ее решения были известны задолго до разработки современных структур данных и современных технологий анализа производительности алгоритмов, еще в те времена, когда поиск MST для графа, скажем, с тысячей ребер, представлял собой крайне сложную задачу. Как мы увидим, некоторые новые алгоритмы построения MST отличаются от старых главным образом способами использования и реализации алгоритмов и структур данных для основных задач, которые (наряду с мощью современных компьютеров) позволяют вычислять MST-деревья с миллионами и даже миллиардами ребер.

Одно из определяющих свойств дерева (см. ) заключается в том, что добавление в дерево любого ребра порождает уникальный цикл. Это свойство лежит в основе доказательства двух фундаментальных теорем об MST-деревьях, которые мы сейчас рассмотрим. Все описанные ниже алгоритмы основаны на этих теоремах или хотя бы одной из них.

Первая из этих теорем, которую мы далее будем называть свойством сечения, относится к идентификации ребер, которые должны входить в MST-дерево заданного графа. Однако для краткой формулировки этого свойства нам понадобятся несколько основных терминов из теории графов.

Иногда мы описываем сечение графа, просто задав множество вершин графа, при этом неявно подразумевается, что сечение содержит это множество и его дополнение. Обычно мы будем использовать такие сечения графа, когда оба множества не пусты — иначе перекрестных ребер не будет.

Если веса ребер графа различны, его MST уникально, а свойство сечения утверждает, что кратчайшее перекрестное ребро для каждого сечения должно входить в MST-дерево. При наличии равных весов может оказаться несколько минимальных секущих ребер. По крайней мере одно из них входит в состав любого заданного MST-дерева, остальные же могут входить, а могут и не входить.

На рис 20.5 представлены несколько примеров свойства сечения. Учтите, что минимальное ребро не обязательно должно быть единственным ребром MST, которое соединяет два множества; в случае обычных сечений существует несколько ребер, соединяющих вершину одного множества с вершиной другого. Если бы существовало лишь одно такое ребро, можно было бы разработать алгоритмы " разделяй и властвуй " на основе походящего выбора множеств, однако это не так.

Эти четыре примера служат иллюстрацией леммы 20.1. Если вершины одного множества закрасить серым цветом, а для другого — белым, то самое короткое ребро, соединяющее серую вершину с белой, принадлежит MST-дереву.

На свойстве сечения основаны алгоритмы вычисления MST-деревьев; кроме того, оно может служить условием оптимальности, которое характеризует MST-деревья. В частности, из него следует, что каждое ребро MST-дерева есть минимальное перекрестное ребро, которое определяется вершинами двух поддеревьев, соединенных этим ребром.

Вторая теорема — свойство цикличности — применяется для выявления ребер, которые не должны входить в MST графа. То есть игнорирование этих ребер не помешает отыскать MST.

Иллюстрация свойства цикла приведена на рис 20.6. Если взять произвольное остовное дерево, добавить в него ребро, образующее цикл, а затем удалить из этого цикла максимальное ребро, то получится остовное дерево, вес которого меньше или равен весу исходного остовного дерева. Вес нового дерева будем меньше веса исходного в том и только том случае, когда добавляемое ребро короче одного из ребер цикла.

После добавления ребра 1-3 в граф с рис 20.1 его MST перестает быть деревом (вверху). Чтобы найти MST нового графа, мы добавляем в MST старого графа новое ребро, которое порождает цикл (в центре). После удаления из цикла самого длинного ребра (4-7) получается MST нового графа (внизу). Один из способов проверить минимальность остовного дерева заключается в проверке, что каждое ребро, не входящее в это MST, имеет наибольший вес в цикле, который оно образует с ребрами дерева. Например, на нижней диаграмме ребро 4-6 имеет максимальный вес в цикле 4-6-7-1-3-4.

Свойство цикла лежит в основе условия оптимальности, которое характерно для MST-деревьев: из него следует, что каждое ребро любого графа, не входящее в заданное MST, является максимальным ребром цикла, который оно образует с ребрами MST.

На свойствах сечения и цикла основаны классические алгоритмы поиска MST-дерева, которые мы будем рассматривать. Мы рассматриваем ребра по одному, проверяя с помощью свойства сечения их пригодность для MST-дерева или с помощью свойства цикла — возможность их отбрасывания. Такие алгоритмы различаются по способам идентификации сечений и циклов.

Первый подход к поиску MST-дерева, который мы подробно рассмотрим — постепенное добавление ребер в MST: сначала выбираем произвольную вершину и рассматриваем ее как MST-дерево, состоящее из одной вершины, затем добавляем к нему V— 1 вершин, каждый раз выбирая минимальное ребро, которое соединяет вершину, уже включенную в MST-дерево, с вершиной, которая еще не содержится в MST. Этот метод известен как алгоритм Прима (Prim), и он будет рассмотрен в разделе 20.3.

Еще один способ вычисления MST-дерева — многократное применение свойства цикла: мы добавляем ребра по одному в заготовку MST-дерева, а если при этом образуется цикл, удаляем из него максимальное ребро (см. упражнения 20.33 и 20.71). Этот метод применяется реже, чем другие рассматриваемые нами алгоритмы — из-за трудности поддержки структуры данных, которая обеспечивает эффективную реализацию операции " удалить из цикла самое длинное ребро " .

Второй подход поиска MST-дерева, который мы подробно рассмотрим — обработка ребер в порядке возрастания их длин (вначале самые короткие) с добавлением в MST каждого ребра, которое не образует цикл с ранее включенными ребрами; процесс останавливается после добавления V— 1 ребер. Этот метод известен как алгоритм Крускала (Kruskal), который будет рассмотрен в разделе 20.4.

Третий подход к построению MST-дерева, который мы подробно изучим в разделе 20.4 — алгоритм Борувки (Boruvka). На первом шаге к MST-дереву добавляются ребра, которые соединяют каждую вершину с ее ближайшим соседом. Если веса ребер различны, этот шаг порождает лес MST-поддеревьев (мы докажем этот факт и рассмотрим усовершенствование, которое позволяет работать даже при наличии ребер с равными весами). Затем мы добавляем в MST ребра, которые соединяют каждую вершину с ее ближайшим соседом (минимальное ребро, соединяющее вершину одного дерева с вершиной другого), и повторяем этот процесс, пока не останется только одно дерево.

В данном графе с четырьмя вершинами все четыре ребра имеют одинаковую длину. Перед соединением каждой вершины с ближайшим соседом необходимо решить, какое ребро выбрать из множества минимальных ребер. В верхнем примере мы выбираем 1 из вершины 0, 2 из 1, 3 из 2 и 0 из 3, что приводит к образованию цикла в заготовке MST-дерева. Каждое из ребер входит в некоторое MST-дерево, но не все они входят в каждое MST. Поэтому мы используем правило разрыва связей (внизу): выбираем минимальное ребро в вершину с наименьшим индексом. Тогда из 1 мы выбираем 0, 0 из 1, 1 из 2 и 0 из 3, что и дает MST-дерево. Цикл разорван, т.к. вершина с максимальным индексом 3 не выбрана ни из одного из ее соседей (2 или 1), а она может выбрать только одного из них (0).

Все эти алгоритмы — специальные случаи общей парадигмы, которой по сей день пользуются разработчики новых алгоритмов построения MST. А именно, мы можем в произвольном порядке применять свойство сечения для выбора того или иного ребра в качестве ребра MST или свойство цикла для отбрасывания ребра и продолжать так, пока не будет возможности увеличить количество принятых или отброшенных ребер. Тогда для любого разбиения множества вершин графа на два подмножества в MST имеется соединяющее их ребро (то есть применение свойства сечения не увеличит количество ребер в MST). И все циклы графа содержат, по меньшей мере, одно ребро, не входящее в MST (то есть применение свойства цикла не увеличит количество ребер, не входящих в MST). Оба эти свойства вместе позволяют вычислить полное MST-дерево.

Точнее, все три алгоритма, которые мы рассмотрим ниже, можно свести к одному обобщенному алгоритму. Этот алгоритм начинается с выбора леса MST-поддеревьев, состоящих из одиночных вершин (и не содержащих ребер), затем выполняется шаг добавления в MST минимального ребра, соединяющего два любых поддерева леса, и эти шаги повторяются V— 1 раз, пока не останется единственное MST-дерево. Согласно свойству сечения, ни одно из ребер, порождающих цикл, не стоит рассматривать в качестве кандидата на включение в MST-дерево, поскольку ранее одно из ребер уже было минимальным ребром, пересекающим некоторое сечение между MST-поддеревьями, содержащими его вершины. В алгоритме Прима ребра добавляются по одному к единственному дереву; алгоритмы Крускала и Борувки объединяют деревья в лесе.

Согласно описанию, приведенному в этом разделе и в классической литературе, для выполнения данных алгоритмов необходимы высокоуровневые абстрактные операции, такие как:

Наша задача заключается в разработке алгоритма и структур данных для эффективной реализации этих операций. К счастью, эта задача позволяет использовать базовые алгоритмы и структуры данных, разработанные ранее в этой книге.

Алгоритмы поиска MST-деревьев имеют долгую и интересную историю, которая еще не закончена; мы будем излагать эту историю по мере изучения конкретных алгоритмов. Развитое за много лет понимание различных методов реализации базовых абстрактных операций не позволяет объективно оценить зарождение этих алгоритмов. Вообще-то они были впервые описаны в двадцатых годах прошлого столетия — то есть до появления компьютеров в современном виде и до появления фундаментальных алгоритмов сортировки и многих других алгоритмов. Как нам теперь известно, выбор базовых алгоритмов и структур данных существенно влияет на производительность, даже при реализации простейших схем вычислений. В последние годы исследования задачи поиска MST-деревьев в основном касаются таких вопросов реализации, где используются все те же классические схемы. Для последовательности и ясности изложения мы будем называть базовые подходы по приведенным здесь именам, хотя их абстрактные версии были рассмотрены намного раньше, и современные реализации используют алгоритмы и структуры данных, разработанные намного позже этих методов.

Алгоритм построения MST-деревьев за линейное время не найден до сих пор. Как мы увидим, многие наши реализации выполняются за линейное время в большом множестве реальных ситуаций, однако в худшем случае эта зависимость уже не линейна. Разработка алгоритмов с гарантированным линейным временем выполнения на разреженных графах все еще остается недостижимой целью.

Помимо естественного поиска алгоритма решения этой фундаментальной задачи, изучение алгоритмов поиска MST подчеркивает важность понимания основных характеристик производительности фундаментальных алгоритмов. Программисты используют алгоритмы и структуры данных все более высокого уровня абстракции, и такие ситуации встречаются все чаще. Наши реализации АТД обладают различным быстродействием, и по мере использования высокоуровневых АТД в качестве компонентов алгоритмов решения задач еще более высокого уровня количество вариантов увеличивается. Алгоритмы, основанные на использовании MST и подобных им абстракций (благодаря эффективным реализациям, которые будут рассмотрены ниже в этой главе), часто используются для решения других задач на еще более высоком уровне абстракции.

Упражнения

20.26. Пронумеруйте (по порядку) от 0 до 5 следующие точки на плоскости:

(1,3) (2,1) (6,5) (3,4) (3,7) (5,3).

Принимая длину ребер в качестве их весов, приведите MST-дерево для графа, заданного множеством ребер

1-03-55-23-45-10-30-44-22-3.

20.27. Предположим, что все ребра графа имеют различные веса. Должно ли самое короткое его ребро принадлежать MST-дереву? Докажите это или приведите контрпример.

20.28. Выполните упражнение 20.27 для самого длинного ребра графа.

20.29. Приведите контрпример, демонстрирующий ошибочность следующей стратегии поиска MST: " Начните с любой вершины, считая ее MST-деревом с одной вершиной, а затем добавьте к этому дереву V— 1 вершину, всегда выбирая следующим минимальное ребро, инцидентное последней включенной в MST вершине " .

20.30. Предположим, что все ребра заданного графа имеют различные веса. Должно ли минимальное в каждом цикле ребро принадлежать MST-дереву? Докажите это утверждение или приведите контрпример.

20.31. Пусть задано MST-дерево для графа G, а затем из графа G удалено некоторое ребро. Опишите, как найти MST для нового графа за время, пропорциональное количеству ребер графа G.

20.32. Постройте MST-дерево, которое получается после многократного применения свойства цикла к графу, изображенному на рис 20.1, если выбирать ребра в указанном порядке.

20.33. Докажите, что многократное применение свойства цикла приводит к построению MST-дерева.

20.34. Опишите, как (при необходимости) адаптировать каждый алгоритм из описанных в данном разделе для решения задачи поиска минимального остовного леса для взвешенного графа (объединение MST-деревьев его связных компонентов).

Алгоритм Прима и поиск по приоритету

Алгоритм Прима, похоже, наиболее прост для реализации из всех алгоритмов поиска MST и рекомендуется для насыщенных графов. В нем используется сечение графа, состоящее из древесных вершин (выбранных для MST) и недревесных вершин (еще не выбранных в MST-дерево). Вначале мы выбираем в качестве MST-дерева произвольную вершину, затем помещаем в MST минимальное перекрестное ребро (которое превращает недревесную вершину MST-дерева в древесную) и повторяем эту же операцию V— 1 раз, пока все вершины не окажутся в дереве.

Из этого описания непосредственно следует примитивная реализация алгоритма Прима. Чтобы найти очередное ребро для включения в MST, необходимо просмотреть все ребра, которые выходят из древесной вершины в недревесную вершину, а затем выбрать из них самое короткое и включить его в MST. Мы не будем рассматривать соответствующую программную реализацию из-за ее крайней неэффективности (см. упражнения 20.35—20.37). Этот алгоритм можно упростить и ускорить с помощью простых структур данных, позволяющих устранить повторные вычисления.

Единичным шагом в алгоритме Прима является добавление вершины в MST-дерево, и прежде чем приступать к реализации, стоит хорошенько разобраться в его сути. Здесь главное — найти кратчайшее расстояние от каждой недревесной вершины до дерева. При присоединении вершины v к дереву единственным возможным изменением для недревесных вершин w является приближение w к дереву. То есть не нужно проверять расстояние от вершины w до всех вершин дерева: достаточно знать минимальное расстояние в каждый момент и проверять, изменяет ли добавление вершины v в дерево это минимальное расстояние.

Для реализации этой идеи нам потребуются такие структуры данных, которые предоставляют следующую информацию:

Простейшей реализацией каждой из этих структур данных будет вектор, индексированный именами вершин (этот вектор можно использовать для хранения древесных ребер, выполняя индексацию по вершинам при их добавлении в дерево). Программа 20.6 представляет собой реализацию алгоритма Прима для насыщенных графов. Она использует для этих трех структур данных векторы mst, fr и wt.

После включения в дерево нового ребра (и вершины) нужно выполнить еще две задачи:

Реализация в программе 20.6 решает обе эти задачи с помощью одного просмотра недревесных вершин. Сначала она обновляет содержимое векторов wt[w] и fr[w], если v-w приближает w к дереву, после чего изменяется текущий минимум, если wt[w] (длина fr[w]) показывает, что w ближе к дереву, чем любая другая недревесная вершина с меньшим индексом.

Программа 20.6. Алгоритм Прима, реализующий построение MST-дерева

Данная реализация алгоритма Прима рекомендуется для работы с насыщенными графами и может применяться для любого представления графа, в котором возможна проверка существования указанного ребра. Внешний цикл наращивает MST-дерево, выбирая минимальные ребра, которые пересекают сечение между вершинами, входящими в MST, и вершинами, не входящими в него. Цикл по w отыскивает минимальное ребро, сохраняя (если w не содержится в MST) условие, что ребро fr[w] является самым коротким (с весом wt[w]) ребром из w в MST

Результатом вычислений является вектор указателей на ребра. Первый указатель (mst[0]) не используется, остальные (от mst[1] до mst[G.V()]) содержат MST-дерево связного компонента графа, которому принадлежит вершина 0.

  template <class Graph, class Edge>
  class MST
    { const Graph G;
      vector<double> wt;
      vector<Edge *> fr, mst;
    public:
      MST(const Graph G) : G(G),
        mst(G.V()), wt(G.V(), G.V()), fr(G.V())
        { int min = -1;
          for (int v = 0; min != 0; v = min)
            { min = 0;
              for (int w = 1; w < G.V(); w++)
                if (mst[w] == 0)
                  { double P; Edge* e = G.edge(v, w);
                    if (e)
                      if ((P = e->wt()) < wt[w])
                        { wt[w] = P; fr[w] = e; }
                    if (wt[w] < wt[min]) min = w;
                 }
              if (min) mst[min] = fr[min];
            }
        }
      void show()
        { for (int v = 1; v < G.V(); v++)
          if (mst[v]) mst[v]->show();
        }
    };
      

На рис 20.8 показан пример построения MST-дерева с помощью алгоритма Прима, а на рис 20.9 показано развертывание MST для более крупного графа.

Программа 20.6 основана на следующем наблюдении: можно чередовать операции поиска минимального ребра и обновления в одном цикле, в котором просматриваются все недревесные ребра. В насыщенных графах количество ребер, которые, возможно, придется просмотреть для обновления расстояния от недревесных вершин до дерева, пропорционально V.

Первым шагом вычисления MST-дерева по алгоритму Прима в это дерево заносится вершина 0. Затем мы находим все ребра, которые соединяют 0 с другими вершинами (еще не включенными в это дерево), и выбираем из них самое короткое (слева вверху). Ребра, соединяющие древесные вершины с недревесными (накопитель), заштрихованы и перечислены под каждым чертежом графа. Для простоты ребра из накопителя перечисляются в порядке возрастания их длины, то есть самое короткое ребро — первое в этом списке. В различных реализациях алгоритма Прима используются различные структуры данных для хранения этого списка и определения минимального ребра. Вторым шагом самое короткое ребро 0-2 переносится (вместе с его конечной вершиной) из накопителя в дерево (вторая диаграмма сверху слева). На третьем шаге ребро 0-7 переносится из накопителя в дерево, в накопителеребро 0-1 заменяется на 7-1, ребро 0-6 на 7-6 (поскольку включение вершины 7 в дерево приближает к дереву вершины 1 и 6), а ребро 7-4 заносится в накопитель (поскольку добавление вершины 7 в дерево превращает 7-4 в ребро, которое соединяет древесную вершину с недревесной) (третья диаграмма сверху слева). Далее, мы переносим в дерево ребро 7-1 (слева внизу). В завершение вычислений мы исключаем из очереди ребра 7-6, 7-4, 4-3 и 3-5, обновляя накопитель после каждой вставки для отражения обнаруженных более коротких или новых путей (справа, сверху вниз).

Ориентированный чертеж растущего MST показан справа от каждого чертежа графа. Ориентация является следствием алгоритма: само MST-дерево обычно рассматривается как неупорядоченное множество неориентированных ребер.

Эта последовательность демонстрирует рост MST-дерева при обнаружении алгоритмом Прима 1/4, 1/2, 3/4 и всех ребер MST-дерева (сверху вниз). Ориентированное представление полного MST-дерева показано справа.

Поэтому поиск ближайшего к дереву недревесного ребра не слишком трудоемок. Но в разреженном графе для выполнения каждой из этих операций может понадобиться значительно менее V шагов. Самое главное при этом — множество ребер-кандидатов для включения в MST, которое мы называем накопителем (fringe). Количество ребер в накопителе обычно существенно меньше количества недревесных ребер, поэтому можно скорректировать описание алгоритма следующим образом. Начинаем с петли исходной вершины в накопителе и до тех пор, пока накопитель не опустеет, выполняем следующие операции:

Переносим минимальное ребро из накопителя в дерево. Посещаем вершину, в которую оно ведет, и помещаем в накопитель все ребра, которые ведут из этой вершины в одну из недревесных вершин, отбрасывая ребро большей длины, если два ребра в накопителе указывают на одну и ту же вершину.

Из этой формулировки ясно, что алгоритм Прима есть ни что иное, как обобщенный поиск на графе (см. ), в котором накопитель представлен очередью с приоритетами на основе операции извлечь минимальное (см. . Мы будем называть обобщенный поиск на графе с очередями с приоритетами поиском по приоритету (priority-first search — PFS). Если в качестве приоритетов использовать веса ребер, то поиск по приоритету реализует алгоритм Прима.

Эта формулировка учитывает важное замечание, которое мы сделали выше в в связи с реализацией поиска в ширину. Еще более простой общий подход — просто хранить все ребра, инцидентные древесным вершинам дерева, чтобы механизм очереди с приоритетами находил самое короткое ребро и игнорировал более длинные (см. упражнение 20.41). Как мы убедились в случае поиска в ширину, этот подход неудобен тем, что структура данных накопителя без необходимости загромождается ребрами, которые никогда не попадут в MST. Размер накопителя может возрасти пропорционально E (вместе с затратами на содержание накопителя такого размера), в то время как поиск по приоритету гарантирует, что накопитель не будет содержать более V вершин.

Как и в случае реализации общего алгоритма, имеется целый ряд возможных подходов для взаимодействия с АТД очереди с приоритетами. Один из подходов использует очередь с приоритетами для ребер так же, как в обобщенном поиске на графах из программы 18.10. Реализация в программе 20.7 по существу эквивалентна программе 18.10, но ориентирована на работу с вершинами, чтобы использовать индексированную очередь с приоритетами (см. ). (Полная реализация конкретного интерфейса очереди с приоритетами, используемого программой 20.7, приведена в программе 20.10 в конце данной главы.) Будем называть краевыми вершинами (fringe vertex) подмножество недревесных вершин, которые соединены ребрами из накопителя с вершинами дерева, и будем использовать те же векторы, индексированные именами вершин — mst, fr и wt — которые применялись в программе 20.6. Очередь с приоритетами содержит индекс каждой краевой вершины, а этот элемент очереди обеспечивает доступ к самому короткому ребру, соединяющему краевую вершину с деревом и содержит длину этого ребра (во втором и третьем векторах).

Первый вызов функции pfs (поиск по приоритету) в конструкторе программы 20.7 находит MST в связном компоненте, содержащем вершину 0, а последующие вызовы находят MST в других связных компонентах. Таким образом, в не связных графах этот класс фактически находит минимальные остовные леса (см. упражнение 20.34).

Программа 20.7. Поиск по приоритету

Функция pfs выполняет обобщенный поиск на графе с использованием накопителя в качестве очереди с приоритетами (см. ). Приоритет P определяется так, чтобы данный класс реализовал алгоритм Прима для вычисления MST; другие определения приоритетов приведут к другим алгоритмам. Главный цикл переносит ребро с максимальным приоритетом (с наименьшим весом) из накопителя в дерево, а затем проверяет все ребра, смежные с только что занесенной в дерево вершиной, чтобы узнать, потребуются ли изменения в накопителе. Ребра, ведущие к вершинам, которые отсутствуют в накопителе и в дереве, заносятся в накопитель, при этом самые короткие ребра в вершины накопителя заменяют соответствующие ребра в накопителе.

Класс PQi представляет собой косвенный интерфейс очереди с приоритетами (см. ), в котором добавлена возможность передачи в конструктор ссылки на массив приоритетов, вызов delmax заменен на getmin, а вызов change — на lower. Реализация этого интерфейса приведена в программе 20.10.

  template <class Graph, class Edge>
  class MST
    { const Graph G;
      vector<double> wt;
      vector<Edge *> fr, mst;
      void pfs(int s)
        { PQi<double> pQ(G.V(), wt);
          pQ.insert(s);
          while (!pQ.empty())
            { int v = pQ.getmin();
              mst[v] = fr[v];
              typename Graph::adjIterator A(G, v);
              for (Edge* e = A.beg(); !A.end(); e = A.nxt())
                { double P = e->wt(); int w = e->other(v) ;
                  if (fr[w] == 0)
                    { wt[w] = P; pQ.insert(w); fr[w] = e; }
                  else if (mst[w] == 0  Р < wt[w])
                    { wt[w] = P; pQ.lower(w); fr[w] = e; }
                }
            }
        }
    public:
      MST(Graph G) : G(G),
        fr(G.V()), mst(G.V()), wt(G.V() , -1)
        { for (int v = 0; v < G.V(); v++)
            if (mst[v] == 0) pfs(v);
        }
    };
      

Поиск по приоритету — подходящее обобщение поиска ширину и поиска в глубину, поскольку эти методы также могут быть получены за счет соответствующей настройки приоритета. Например, мы можем (правда, не вполне естественно) использовать переменную , формальное доказательство эквивалентности требует особого внимания к правилам замены, чтобы получить ту же последовательность вершин, что и при работе классических алгоритмов.

Как мы увидим, поиск по приоритетам охватывает не только поиск в глубину, поиск в ширину и алгоритм Прима для вычисления MST-дерева, но и несколько других классических алгоритмов. Все эти алгоритмы отличаются только функциями вычисления приоритетов. Поэтому время их выполнения зависит от производительности АТД очереди с приоритетами. Известен общий результат, который охватывает не только две рассмотренные нами реализации алгоритма Прима, но также и широкий класс фундаментальных алгоритмов обработки графов.

В частности, использование реализации очереди с приоритетами с помощью неупорядоченного массива дает оптимальное решение для насыщенных графов с такой же производительностью в худшем случае, что и классическая реализация алгоритма Прима (программа 20.6). То есть леммы 20.6 и 20.7 представляют собой частные случаи леммы 20.8; на протяжении этой книги нам встретятся и другие многочисленные алгоритмы, которые отличаются друг от друга только выбором функций вычисления приоритетов и реализациями очередей с приоритетами.

Свойство 20.7 представляет собой важный общий результат: устанавливаемая им временная граница есть верхняя граница для худшего случая, которая для широкого класса задач обработки графов гарантирует производительность, отличающуюся от оптимальной (линейное время) не более чем в и рис 20.11), а некоторые операции для очередей с приоритетами требуют гораздо менее lgV шагов.

Этот эффект заметен, но обычно увеличивает время выполнения лишь на небольшой постоянный коэффициент. Например, доказательство того, что накопитель не сможет содержать более вершин, улучшит граничное значение только в два раза. Но более важно то, что обычно количество операций уменьшить ключ намного меньше E, поскольку эти операции выполняются только при обнаружении ребра в узел, содержащийся в накопителе, которое короче кратчайшего до этого ребра такого же типа. Это происходит довольно редко: большая часть ребер никак не влияет на очередь с приоритетами (см. упражнение 20.40). Поиск по приоритету вполне можно считать линейным — кроме случаев, когда V lgV значительно больше E.

Нижний график показывает размеры накопителя при работе PFS для примера с рис 20.10. Выше для сравнения приведены графики для поиска в глубину, рандомизированного поиска и поиска с рис 18.28.

АТД очереди с приоритетами и абстракции обобщенного поиска на графах позволяют понять взаимосвязь между различными алгоритмами. Поскольку эти абстракции (и программные механизмы, обеспечивающие поддержку их использования) были разработаны спустя много лет после базовых методов, соответствие алгоритмов их классическим описаниям может интересовать разве что историков. Но все же знание всех основных исторических фактов полезно, когда мы сталкиваемся с описаниями алгоритмов построения MST в исследовательских работах или в других текстах, а понимание того, как эти немногочисленные простые абстракции связывают работы многих исследователей, разделенные многими десятилетиями, убедительно доказывает их ценность и мощь. Поэтому мы кратко рассмотрим происхождение этих алгоритмов.

Реализация MST для насыщенных графов, которая фактически эквивалентна программе 20.6, была впервые опубликована Примом (Prim) в 1961 г. и, несколько позже и независимо от него, Дейкстрой (Dijkstra). Обычно она называется алгоритмом Прима, хотя формулировка Дейкстры была более общей — поэтому некоторые ученые считают алгоритм вычисления MST специальным случаем алгоритма Дейкстры. Однако основная идея была высказана Ярником (Jarnik) еще в 1939 г., так что некоторые авторы называют этот метод алгоритмом Ярника, считая, что Прим (а также Дейкстра) просто разработал эффективную реализацию алгоритма для насыщенных графов. После распространения АТД очередей с приоритетами в начале 1970-х годов применение этого алгоритма для вычисления MST на разреженных графах уже не представляло трудности. Широко известный факт, что MST для разреженных графов можно вычислить за время, пропорциональное E lgV, не связан с именем какого-либо исследователя. Как будет показано в разделе 20.6, с тех пор многие исследователи направили свои усилия на поиск эффективных реализаций как ключевого момента отыскания эффективных алгоритмов построения MST для разреженных графов.

Упражнения

20.35. Оцените производительность примитивной реализации алгоритма Прима, описанной в начале данного раздела, для графа с Vвершинами. Указание. При решении этой задачи может пригодиться комбинаторная сумма:

$$$$\sum \limits_{1\leq k\leq V} k(V-k}=(V+1)V(V-1)\6$$$$

20.36. Выполните упражнение 20.35 для графов, у которых все вершины имеют одну и ту же фиксированную степень t.

20.37. Выполните упражнение 20.35 для разреженных графов общего вида с V вершинами и E ребрами. Поскольку время выполнения зависит от весов ребер и степеней вершин, проведите анализ для худшего случая. Приведите семейство графов, для которого действительна ваша оценка для худшего случая.

20.38. Представьте в стиле рис 20.8 результаты вычисления MST-дерева с помощью алгоритма Прима для сети, определенной в упражнении 20.26.

20.39. Опишите семейство графов c Vвершинами и E ребрами, для которого достигается оценка времени выполнения алгоритма Прима с поиском по приоритетам в худшем случае.

20.40. Разработайте походящий генератор случайных графов с V вершинами и E ребрами, чтобы время выполнения алгоритма Прима с поиском по приоритетам (программа 20.7) было нелинейным.

20.41. Измените программу 20.7, чтобы она работала так же, как и программа 18.8, то есть хранила в накопителе все ребра, инцидентные древесным вершинам. Эмпирически сравните полученную реализацию с программой 20.7 для различных взвешенных графов (см. упражнения 20.9-20.14).

20.42. Выведите из интерфейса, определенного в программе 9.12, реализацию очереди с приоритетами для использования в программе 20.7 (чтобы было возможно использование любой реализации этого интерфейса).

20.43. Воспользуйтесь контейнером priority_queue из библиотеки STL для реализации интерфейса очереди с приоритетами, который применяется в программе 20.7.

20.44. Предположим, что вы используете реализацию очереди с приоритетами, в которой применяется сортированный список. Каким будет время выполнения в худшем случае для графа с V вершинами и с E ребрами (с точностью до постоянного множителя)? В каких случаях этот метод можно будет применять, и можно ли вообще? Обоснуйте свой ответ.

20.45. Ребро MST, удаление которого из графа приводит к увеличению веса MST, называется критическим ребром. Покажите, как найти все критические ребра в графе за время, пропорциональное E lgV.

20.46. Эмпирически сравните производительность программы 20.6 с производительностью программы 20.7, используя реализацию очереди с приоритетами в виде неупорядоченного массива для различных взвешенных графов (см. упражнения 20.9-20.14).

20.47. Эмпирически определите эффект использования в программе 20.7 реализации очереди с приоритетами на основе турнира индексного пирамидального дерева (см. упражнение 9.53) вместо программы 9.12 для различных взвешенных графов (см. упражнения 20.9-20.14).

20.48. Эмпирически проанализируйте веса деревьев (см. упражнение 20.23) как функции от V для различных взвешенных графов (см. упражнения 20.9-20.14).

20.49. Эмпирически проанализируйте максимальный размер накопителя как функции от V для различных взвешенных графов (см. упражнения 20.9-20.14).

20.50. Эмпирически проанализируйте высоту дерева как функции от V для различных взвешенных графов (см. упражнения 20.9-20.14).

20.51. Эмпирически определите зависимость результатов выполнения упражнений 20.49 и 20.50 от выбора исходной вершины. Будет ли лучше, если выбирать ее случайно?

20.52. Напишите клиентскую программу, которая выполняет динамическую графическую анимацию алгоритма Прима. Программа должна строить изображения наподобие рис. 20.10 рис 20.10 (см. упражнения 17.56-17.60). Проверьте работу программы на случайных евклидовых графах с соседними связями и на решетчатых графах (см. упражнения 20.17 и 20.19), используя столько точек, сколько можно обработать за приемлемое время.

Алгоритм Крускала

Алгоритм Прима строит минимальное остовное дерево по одному ребру, находя на каждом шаге ребро, которое присоединяется к единственному растущему дереву. Алгоритм Крускала также строит MST, добавляя к нему по одному ребру, но в отличие от алгоритма Прима, он отыскивает ребро, которое соединяет два дерева в лесу, образованном растущими MST-поддеревьями. Построение начинается с вырожденного леса из V деревьев (каждое состоящее из одной вершины), а затем выполняется операция объединения двух деревьев (самыми короткими ребрами), пока не останется единственное дерево — MST.

На рис 20.12 показан пример пошагового выполнения алгоритма Крускала; рис 20.13 демонстрирует динамические характеристики этого алгоритма на более крупном примере. Разобщенный лес MST-поддеревьев постепенно объединяется в единственное дерево.

Пусть задан список ребер графа в произвольном порядке (левый список ребер). На первом шаге алгоритма Крускала они сортируются по весам (правый список ребер). Затем мы просматриваем ребра этого списка в порядке возрастания их весов, добавляя в MST ребра, которые не создают в нем циклов. Сначала мы добавляем ребро 5-3 (самое короткое ребро), потом 7-6 (слева), затем 0-2 (справа вверху) и 0-7 (справа, вторая диаграмма сверху). Ребро 0-1 со следующим по величине весом создает цикл и поэтому не добавляется в дерево. Ребра, которые не включаются в MST, выделены в отсортированном списке серым цветом. Затем мы добавляем ребро 4-3 (справа, третья диаграмма сверху). Далее мы отбрасываем ребро 5-4, поскольку оно образует цикл, и потом добавляем 7-4 (справа внизу). Когда MST-дерево готово, любое ребро с большим весом образует цикл и поэтому будет отброшено (алгоритм останавливается, когда в MST будут включены V— 1 ребер). В отсортированном списке эти ребра помечены звездочками.

Ребра добавляются в MST-дерево в порядке возрастания их длины — таким образом, лес содержит вершины, соединенные друг с другом относительно короткими ребрами. В любой момент выполнения алгоритма каждая вершина расположена ближе к некоторой вершине своего поддерева, чем к любой другой вершине, не входящей в это дерево.

Алгоритм Крускала прост в реализации — при наличии базовых алгоритмических инструментов, рассмотренных ранее в данной книге. Можно использовать любую сортировку из описанных в части 3 для упорядочения ребер по весу и любой из алгоритмов решения задачи связности из для удаления циклообразующих ребер. Программа 20.8 содержит соответствующую реализацию функции построения MST для АТД графа, которая функционально эквивалентна другим реализациям MST, рассмотренным в данной главе. Эта реализация не зависит от представления графа: она вызывает клиентскую программу GRAPH, чтобы получить вектор, содержащий ребра графа, а затем на основе этого вектора строит MST-дерево.

Обратите внимание, что существуют два способа окончания работы алгоритма Крускала. Если мы найдем .

Эта последовательность показывает 1/4, 1/2, 3/4 и полное MST по мере его роста.

Программа 20.8. Алгоритм Крускала вычисления MST

Для отыскания MST эта реализация использует АТД сортировки из и АТД объединения-поиска из , рассматривая ребра в порядке возрастания их весов и отбрасывая те ребра, которые образуют циклы, пока не будут найдены V— 1 вершин, составляющих остовное дерево.

Здесь не показан класс-оболочка EdgePtr, позволяющий функции sort сравнивать указатели на ребра с помощью перегруженной операции <, как описано в , и вариант программы 20.2 с третьим шаблонным аргументом.

  template <class Graph, class Edge, class EdgePtr>
  class MST
    { const Graph G;
      vector<EdgePtr> a, mst;
      UF uf;
    public:
      MST(Graph G) : G(G), uf(G.V()), mst(G.V())
        { int V = G.V(), E = G.E();
          a = edges<Graph, Edge, EdgePtr>(G);
          sort<EdgePtr>(a, 0, E-1);
          for (int i = 0, k = 1; i < E  k < V; i++)
            if (!uf.find(a[i]->v, a[i]->w))
              { uf.unite(a[i]->v, a[i]->w);
                mst[k++] = a[i];
              }
        }
    };
      

Анализ времени выполнения алгоритма Крускала не представляет трудностей, т.к. известно время выполнения составляющих его операций АТД.

Сравнение производительности алгоритмов Крускала и Прима будет выполнено в разделе 20.6. А пока учтите, что время выполнения, пропорциональное E lgE, не обязательно хуже, чем ElgV: т.к. E не превышает V², то lgE не превосходит 2 lgV Различия в производительности для конкретных графов обусловлены особенностями реализации и тем, приближается ли фактическое время выполнения к граничным значениям для худшего случая.

На практике можно воспользоваться быстрой сортировкой или быстрой системной сортировкой (которая обычно основана на быстрой сортировке). Теоретически такой подход может быть непривлекательным из-за квадратичной трудоемкости сортировки в худшем случае, однако обычно при этом время выполнения уменьшается. Хотя вообще-то можно воспользоваться поразрядной сортировкой, чтобы выполнить упорядочение ребер за линейное время (при определенных ограничениях на веса ребер) — тогда будут превалировать затраты на выполнение E операций найти. Это позволит изменить формулировку леммы 20.9: при выполнении заданных ограничений на веса ребер время выполнения алгоритма Крускала не превышает $$$Elg^{ullet }E$$$ с некоторым постоянным коэффициентом (см. ). Напомним, что функция $$$lg^{ullet }E$$$ равна количеству итераций двоичной логарифмической функции, прежде чем результат станет меньше единицы; это значение меньше 5, если E меньше 2⁶⁵⁵³⁶. То есть такая корректировка делает алгоритм Крускала по сути линейным в большинстве практических ситуаций.

Обычно трудоемкость вычисления MST с помощью алгоритма Крускала даже меньше стоимости обработки всех ребер, поскольку построение завершается задолго до того, как будет просмотрена значительная часть всех ребер (длинного) графа. Этот факт позволяет существенно уменьшить время выполнения во многих практических ситуациях, если вообще не включать в сортировку все ребра, длина которых превышает длину самого длинного ребра MST. Один из самых простых способов достижения этой цели — использование очереди с приоритетами, в реализации которой имеется операция создать с линейным временем выполнения и операция извлечь минимальное с логарифмическим временем.

Например, таких характеристик производительности можно достичь с помощью стандартной реализации пирамидального дерева, используя восходящее построение (см. ). При этом в программу 20.8 нужно внести следующие изменения: вызов sort заменить вызовом pq.construct(), чтобы строить пирамидальное дерево за время, пропорциональное E, добавить во внутренний цикл отбор из очереди с приоритетами самых коротких ребер, для которых e = pq.delmin(), и заменить все обращения к a[i] на e.

Эта же идея позволяет получить аналогичные преимущества и в реализации на основе быстрой сортировки. Рассмотрим, что произойдет, если использовать прямую рекурсивную быструю сортировку, где выполняется разбиение по i-му элементу с последующей рекурсивной сортировкой подфайла слева от i и подфайла справа от i. В силу построения алгоритма после завершения первого рекурсивного вызова первые i элементов уже упорядочены (см. программу 9.2). Этот очевидный факт позволяет получить быструю реализацию алгоритма Крускала: если поместить проверку, порождает ли ребро a[i] цикл, между рекурсивными вызовами, то получится алгоритм, который, по построению, после завершения первого рекурсивного вызова уже проверил первые i ребер (в порядке возрастания весов)! Если добавить проверку на прекращение работы после выявления V- 1 ребер MST-дерева, то получается алгоритм, который сортирует лишь столько ребер, сколько их необходимо для вычисления MST-дерева, плюс несколько дополнительных этапов разбиения с участием больших элементов (см. упражнение 20.57). Как и в случае простых реализаций сортировки, этот алгоритм может потребовать квадратичного времени выполнения в худшем случае, однако имеется вероятностная гарантия того, что время выполнения в худшем случае не будет близким к такому пределу. Кроме того, подобно простым реализациям сортировки, эта программа из-за более короткого внутреннего цикла обычно работает быстрее реализации на основе пирамидального дерева.

Если же граф не является связным, то версия алгоритма Крускала на основе частичной сортировки не дает никаких преимуществ, поскольку в этом случае приходится просматривать все ребра графа. Даже в случае связного графа самое длинное ребро может оказаться в MST-дереве, и тогда любая реализация метода Крускала должна просмотреть все ребра. Например, граф может состоять из плотных кластеров вершин, соединенных внутри короткими ребрами, и только одна из вершин кластера соединена с " внешней " вершиной длинным ребром. Несмотря на возможность таких нетипичных вариантов, подход с применением частичной сортировки достоин внимания, поскольку дает существенный выигрыш и не требует больших дополнительных затрат (или вовсе никаких).

Интересны и поучительны и исторические сведения. Крускал предложил свой алгоритм в 1956 г., однако, опять-таки, в течение многих лет не были подробно изучены соответствующие реализации АТД. Поэтому характеристики производительности реализаций, таких как версия программы 20.8 с очередью с приоритетами, не получили надлежащей оценки вплоть до 1970-х годов. Еще один интересный исторический факт: в статье Крускала упоминалась версия алгоритма Прима (см. упражнение 20.59), а Борувка описал в своей статье оба эти подхода. Эффективные реализации метода Крускала для разреженных графов появились раньше реализаций метода Прима для разреженных графов — потому что АТД поиска-объединения (и сортировки) стали применяться раньше, чем АТД очереди с приоритетами. По существу, прогресс в современном состоянии алгоритма Крускала, как и реализации алгоритма Прима, обусловлен главным образом повышением производительности АТД. С другой стороны, возможность применения абстракции поиска-объединения в алгоритме Крускала и возможность применения абстракции очереди с приоритетами в алгоритме Прима стали для многих исследователей основным стимулом для поиска более совершенных реализаций этих АТД.

Упражнения

20.53. Покажите в стиле рис 20.12 результат вычисления алгоритмом Крускала MST-дерева для сети, определенной в упражнении 20.26.

20.54. Эмпирически определите для различных видов взвешенных графов длину самого длинного ребра MST-дерева и количество ребер графа, длина которых не превосходит длины этого ребра (см. упражнения 20.9—20.14).

20.55. Разработайте реализацию АТД объединения-поиска, в которой операция найти выполняется за постоянное время, а операция объединить — за время, пропорциональное lgV.

20.56. Эмпирически сравните для различных видов взвешенных графов реализацию АТД из упражнения 20.55 со взвешенным объединением-поиском с делением пополам (программа 1.4), когда алгоритм Крускала является клиентской программой (см. упражнения 20.9—20.14). Выделите затраты на сортировку ребер отдельно, чтобы можно было изучать влияние замены на общие затраты и на часть расходов, связанных с АТД объединения-поиска.

20.57. Разработайте реализацию на основе описанной в тексте идеи: интеграции алгоритма Крускала с быстрой сортировкой, чтобы проверять каждое ребро на принадлежность MST-дереву сразу после проверки всех ребер с меньшими весами.

20.58. Добавьте в алгоритм Крускала реализации двух функций АТД, которые заполняют вектор, индексированный именами вершин, который поставляется клиентской программой. Этот вектор разбивает вершины на к таких кластеров, что ни одно ребро с длиной, большей d, не соединяет две вершины из различных кластеров. Первая функция принимает в качестве аргумента к и возвращает d, а вторая принимает в качестве аргумента d и возвращает к. Протестируйте полученную программу для различных к и d на случайных евклидовых графах с соседними связями и на решетчатых графах (см. упражнения 20.17 и 20.19) различных размеров.

20.59. Разработайте реализацию алгоритма Прима, основанного на предварительной сортировке ребер.

20.60. Напишите клиентскую программу, которая выполняет динамическую графическую анимацию алгоритма Крускала (см. упражнение 20.52). Проверьте полученную программу на случайных евклидовых графах с соседними связями и на решетчатых графах (см. упражнения 20.17 и 20.19) , используя столько точек, сколько можно обработать за приемлемое время.

Алгоритм Борувки

Следующий алгоритм вычисления MST, который мы рассмотрим, также является самым старым. Подобно алгоритму Крускала, мы строим MST, добавляя ребра в расширяющийся лес MST-поддеревьев, но делаем это поэтапно, добавляя в MST по нескольку ребер. На каждом этапе мы отыскиваем наиболее короткое ребро, которое соединяет каждое MST-поддерево с каким-то другим, а затем включаем все такие ребра в MST.

И опять разработанный в АТД объединения-поиска позволяет получить эффективную реализацию. Для рассматриваемой задачи лучше расширить интерфейс этого АТД, чтобы операция найти была доступна в клиентских программах. Мы будем пользоваться этой функцией для присваивания индекса каждому поддереву, чтобы можно было быстро определить, к какому поддереву принадлежит заданная вершина. Это позволит нам эффективно реализовать все операции, необходимые для работы алгоритма Борувки.

Вначале мы строим вектор, индексированный именами вершин, который для каждого MST-поддерева определяет ближайшего соседа. Затем для каждого ребра графа мы выполняем следующие операции:

После просмотра всех ребер графа вектор ближайших соседних вершин содержит информацию, которая нужна для соединения поддеревьев. Для каждого индекса вершины мы выполняем операцию объединить, чтобы соединить ее с ближайшей соседней вершиной. На следующем этапе мы отбрасываем все более длинные ребра, которые соединяют другие пары вершин в уже соединенных MST-поддеревьях. Работа нашего алгоритма продемонстрирована на рис 20.14 и 20.15.

Программа 20.9 представляет собой непосредственную реализацию алгоритма Борувки. Ее эффективность обусловлена тремя следующими главными факторами:

На верхней диаграмме показаны ориентированные ребра, проведенные из каждой вершины к ближайшему соседу. Из этой диаграммы следует, что ребра 0-2, 1-7 и 3-5 являются самыми короткими ребрами, инцидентными обеим их вершинам, 6-7 — кратчайшее ребро для вершины 6, а 4-3 — кратчайшее ребро для вершины 4. Все эти ребра принадлежат MST и образуют лес MST-поддеревьев (в центре), вычисляемый на первом этапе выполнения алгоритма Борувки. На втором этапе алгоритм завершает вычисление MST-поддеревьев (внизу). Для этого добавляет-сяребро 0-7 — кратчайшее ребро, инцидентное каждой вершине тех поддеревьев, которые оно соединяет; и ребра 4-7 — кратчайшее ребро, инцидентное каждой вершине нижнего поддерева.

Здесь показано содержимое массива объединения-поиска, соответствующего примеру с рис 20.14. Первоначально каждый элемент содержит свой собственный индекс, что означает лес изолированных вершин. После выполнения первого этапа мы получаем три компонента, представленные вершинами 0, 1 и 3 (для такого маленького примера все деревья объединения-поиска являются плоскими). По окончании второго этапа остается единственный компонент, представленный вершиной 1.

Программа 20.9. Алгоритм Борувки вычисления MST

Эта реализация алгоритма Борувки вычисления MST использует версию АТД объединения-поиска из (в интерфейс добавлена функция find с одним аргументом), которая связывает индексы с MST-поддеревьями по мере их построения. На каждом этапе проверяются все оставшиеся ребра, и те, которые соединяют отдельные поддеревья, сохраняются до следующего этапа. Массив a содержит еще не отброшенные ребра, которые пока не включены в MST-поддеревья. Индекс N используется для хранения ребер, отложенных до следующего этапа (в конце каждого этапа в E заносится значение N), а индекс h используется для доступа к следующему проверяемому ребру. Ближайший сосед каждого компонента хранится в массиве b с find номерами компонентов в качестве индексов. В конце каждого этапа каждый компонент соединяется с ближайшим соседним, а ребра ближайшей соседней вершины добавляются в дерево MST.

  template <class Graph, class Edge>
  class MST
    { const Graph G;
      vector<Edge *> a, b, mst;
      UF uf;
    public:
      MST(const Graph G): G(G), uf(G.V()), mst(G.V()+1)
        { a = edges<Graph, Edge>(G);
          int N, k = 1;
          for (int E = a.size(); E != 0; E = N)
            { int h, i, j;
              b.assign(G.V(), 0);
              for (h = 0, N = 0; h < E; h++)
                { Edge *e = a[h];
                  i = uf.find(e->v()), j = uf.find(e->w());
                  if (i == j) continue;
                  if (!b[i] || e->wt() < b[i]->wt()) b[i] = e;
                  if (!b[j] || e->wt() < b[j]->wt()) b[j] = e;
                  a[N++] = e;
                }
              for (h = 0; h < G.V(); h++)
                if (b[h])
                  if (!uf.find(i = b[h]->v(), j = b[h]->w()))
                    { uf.unite(i, j); mst[k++] = b[h]; }
             }
        }
    };
      

Все эти факторы трудно оценить точно, однако нетрудно установить следующую границу.

Оценка времени, приведенная в лемме 20.11, представляет собой осторожную верхнюю границу, поскольку в ней не учитывается существенное уменьшение количества ребер на каждом этапе. На ранних этапах операция найти выполняется за постоянное время, а на последних этапах остается совсем немного ребер. Для многих графов количество ребер экспоненциально убывает в зависимости от количества вершин, а общее время выполнения пропорционально E. Например, как показано на рис 20.16, рассматриваемый алгоритм находит MST нашего большого демонстрационного графа всего за четыре этапа.

Для построения MST в данном примере достаточно всего четырех этапов (сверху вниз).

Множитель $$$lg^{ullet }E$$$ можно устранить, и тогда теоретическая граница времени выполнения алгоритма Борувки еще уменьшится и станет пропорциональна E lgV. Для этого вместо использования операций объединить и найти необходимо представить MST-поддеревья в виде двухсвязных списков. Однако это усовершенствование гораздо сложнее для реализации, а возможное повышение производительности не настолько заметно, чтобы стоило применять его на практике (см. упражнения 20.66 и 20.67).

Как было сказано, алгоритм Борувки — самый старый алгоритм из рассматриваемых нами: его идея впервые была выдвинута в 1926 г. для управления распределением электроэнергии. Затем он был заново открыт Сойеном (Sollin) в 1961 г.; а позже он привлек к себе внимание как основа для алгоритмов вычисления MST с эффективной асимптотической производительностью и как основа для алгоритмов параллельного построения MST.

Упражнения

20.61. Покажите в стиле рис 20.14 результат вычисления алгоритмом Борувки MST для сети, определенной в упражнении 20.26.

20.62. Почему программа 20.9 выполняет проверку операции найти перед выполнением операции объединить? Указание. Рассмотрите ребра одинаковой длины.

20.63. Объясните, почему в программе 20.9 в проверке, защищающей операцию найти, значение b(h) может быть пустым.

20.64. Опишите семейство графов с Vвершинами и E ребрами, для которых количество ребер, которые остаются после каждого этапа алгоритма Борувки, достаточно велико для того, чтобы время выполнения было равно времени для худшего случая.

20.65. Разработайте реализацию алгоритма Борувки, основанную на предварительной сортировке ребер.

20.66. Разработайте реализацию алгоритма Борувки, который использует для представления MST-поддеревьев двухсвязные кольцевые списки, чтобы на каждом этапе можно было выполнять слияние и переименование поддеревьев за время, пропорциональное E (тогда АТД отношения эквивалентности не нужен).

20.67. Эмпирически сравните реализацию алгоритма Борувки из упражнения 20.66 с реализацией, приведенной в тексте (программа 20.9) для различных взвешенных графов (см. упражнения 20.9—20.14).

20.68. Составьте на основе эмпирических данных таблицу с количеством этапов и количеством ребер, обрабатываемых на каждом этапе в алгоритме Борувки для различных взвешенных графов (см. упражнения 20.9—20.14).

20.69. Разработайте реализацию алгоритма Борувки, которая на каждом этапе строит новый граф (по одной вершине для каждого дерева в лесе).

20.70. Напишите клиентскую программу, которая выполняет динамическую графическую анимацию алгоритма Борувки (см. упражнения 20.52 и 20.60). Проверьте полученную программу на случайных евклидовых графах с соседними связями и на решетчатых графах (см. упражнения 20.17 и 20.19) , используя столько точек, сколько можно обработать за приемлемое время.

Сравнения и усовершенствования

Значения времени выполнения рассмотренных базовых алгоритмов вычисления MST приведены в таблице 20.1, а в таблице 20.2 собраны результаты эмпирического сравнения этих алгоритмов. Эти данные показывают, что реализация алгоритма Прима для матрицы смежности лучше подходит для насыщенных графов, что все другие методы отличаются по производительности от наилучшего результата лишь небольшими постоянными множителями (время на извлечение ребер) для графов средней насыщенности, и что метод Крускала сводит задачу к сортировке для разреженных графов.

В общем, для практических целей задачу вычисления MST можно считать " решенной " . Для большинства графов трудоемкость нахождения MST-дерева лишь ненамного превышает затраты на извлечение ребер графа. Это правило не распространяется на крупные очень разреженные графы, но даже и в этом случае производительность может быть повышена примерно в 10 раз по сравнению с лучшими из других известных алгоритмов. Результаты, приведенные в таблице 20.2, зависят от модели, использованной для генерирования графов, хотя они характерны и для многих других моделей (см., например, упражнение 20.80). Однако теоретические результаты не отрицают существования алгоритмов с гарантированным линейным временем выполнения на всех графах. Здесь мы просто ознакомимся с обширными исследованиями по совершенствованию реализаций этих методов.

Здесь приведены значения трудоемкости (в худшем случае) различных алгоритмов вычисления MST-дерева для алгоритмов, рассмотренных в данной главе. Все формулы выведены в предположении, что MST существует (то есть E > V— 1), и имеются Xребер, длина которых не больше длины самого длинного ребра в MST (см. лемму 20.10). Эти граничные значения для худшего случая могут оказаться слишком осторожными для прогнозирования трудоемкости обработки реальных графов. В большом количестве реальных ситуаций время выполнения алгоритмов почти линейно.

Прежде всего, обширные исследования привели к разработке более совершенных реализаций очереди с приоритетами. Расширение биномиальной очереди — пирамидальное дерево Фибоначчи (Fibonacci heap) — достигает теоретически оптимальной производительности, выполняя операции уменьшить ключ за постоянное время и операции извлечь минимальное за логарифмическое время, что, в соответствие с леммой 20.8, приводит к выполнению алгоритма Прима за время, пропорциональное E + VlgV Пирамидальные деревья Фибоначчи более сложны, чем биномиальные очереди, и не совсем удобны для работы, а некоторые из простых реализации очередей с приоритетами имеют похожие характеристики производительности (см. раздел ссылок).

Один из эффективных подходов — применение поразрядных методов в реализации очереди с приоритетами. По производительности такие методы обычно эквивалентны методу Крускала с поразрядной сортировкой или даже применению поразрядной быстрой сортировки для метода с частичным упорядочением, который был рассмотрен в разделе 20.4.

Одним из наиболее эффективных является другой давно известный простой подход, предложенный Д. Джонсоном (D. Jonhson) в 1977 г.: реализация очереди с приоритетами для алгоритма Прима с помощью d-арных пирамидальных деревьев, а не стандартных бинарных пирамидальных деревьев (см. рис 20.17).

Здесь приведены относительные значения времени выполнения различных алгоритмов вычисления MST для случайных взвешенных графов разной насыщенности. При малых плотностях лучше работает алгоритм Крускала, поскольку в нем задействована быстрая сортировка. При большой насыщенности лучшей является классическая реализация алгоритма Прима, поскольку в ней нет обработки списков. Для графов средней плотности реализация алгоритма Прима с поиском по приоритету выполняется за время, необходимое для проверки каждого ребра графа, с небольшим постоянным коэффициентом.

Программа 20.10 представляет собой полную реализацию используемого нами интерфейса очереди с приоритетами, которая основана на этом методе. При такой реализации очереди с приоритетами операция уменьшить ключ выполняется менее чем за logdV шагов, а операция извлечь минимальное — за время, пропорциональное $$$d log_{d}{V}$$$. Тогда, согласно лемме 20.8, время выполнения алгоритма Прима будет пропорционально $$$Vd log_{d}{V} + E log_{d}{V}$$$, т.е. линейно для не разреженных графов.

Если E пропорционально $$$V^{1+\varepsilon}$$$, то из леммы 20.12 следует, что время выполнения в худшем случае пропорционально $$$E/\varepsilon$$$, а это значение линейно при любом значении константы $$$\varepsilon$$$. Например, если количество ребер пропорционально V^3/2, то затраты меньше 2E; если количество ребер пропорционально V^4/3, то затраты меньше 3E; а если количество ребер пропорционально V^5/4, то затраты не превышают 4E. Для графа с одним миллионом вершин и насыщенностью не более 10 затраты меньше 6E.

Соблазн минимизировать таким способом граничное значение времени выполнения в худшем случае упирается в понимание, что часть $$$Vd log_{d}{V}$$$ никуда девать не удастся (для операции извлечь минимальное необходимо просмотреть d потомков при спуске по пирамидальному дереву), хотя часть $$$E log_{d}{V}$$$ вряд ли будет достижима (т.к. большая часть ребер не требует обновления очереди с приоритетами, как было показано при обсуждении вслед за леммой 20.8).

Для типичных графов, наподобие задействованных в экспериментах для таблицы 20.2, уменьшение d не влияет на время выполнения, а использование больших значений d может слегка замедлить реализацию. Однако элементарная защита от худшей производительности делает целесообразной реализацию этого метода в силу ее простоты. В принципе, можно настроить реализацию так, чтобы можно было выбирать оптимальное значение d для некоторых видов графов (выбирайте наибольшее значение, которое не замедляет алгоритм), но вполне подойдет и небольшое фиксированное значение (например, 3, 4 или 5), за исключением, разве что, отдельных крупных классов графов с нетипичными характеристиками.

Если хранить стандартное бинарное пирамидально упорядоченное полное дерево в массиве (вверху), то для перехода из узла i вниз по дереву в его дочерние узлы 2i и 2i + 1 и вверх по дереву к его предку i/2 используются неявные ссылки. В 3-арном пирамидальном дереве (в центре) неявными ссылками узла i являются ссылки на дочерние узлы 3i — 1, 3i и 3i + 1 и на родительский узел $$$\lfloor (i+1)/3\rfloor$$$. Наконец, в 4- арном пирамид-лальном дереве (внизу) неявными ссылками узла i являются ссылки на дочерние узлы 4i — 2, 4i — 1, 4i и 4 i + 1 и на родительский узел $$$\lfloor (i+2)/4\rfloor$$$. Увеличение коэффициента ветвления в реализации неявного пирамидального дерева может оказаться полезным в приложениях, подобных алгоритму Прима, где требуется выполнение большого количества операций уменьшить ключ.

Программа 20.10. Реализация очереди с приоритетами на основе многопутевого пирамидального дерева

Этот класс использует многопутевые пирамидальные деревья для реализации косвенного интерфейса очереди с приоритетами, который используется в данной книге. В его основе лежат следующие изменения, внесенные в программу 9.12: конструктор принимает ссылку на вектор приоритетов, вместо delmax и change реализованы функции getmin и lower, и обобщены функции fixUp и fixDown, чтобы они могли поддерживать пирамидальное d-дерево. В силу последнего изменения операция извлечь минимальное выполняется за время, пропорциональное $$$d log_{d}{V}$$$ , но операция уменьшить ключ выполняется менее чем за $$$log_{d}{V}$$$ шагов.

  template <class keyType>
  class PQi
    { int d, N;
      vector<int> pq, qp;
      const vector<keyType> a;
      void exch(int i, int j)
        { int t = pq[i]; pq[i] = pq[j]; pq[j] = t;
          qp[pq[i]] = i; qp[pq[j]] = j;
        }
      void fixUp(int k)
        { while (k > 1  a[pq[(k+d-2)/d]] > a[pq[k]])
            { exch(k, (k+d-2)/d); k = (k+d-2)/d; }
        }
      void fixDown(int k, int N)
        { int j;
          while ((j = d*(k-1)+2) <= N)
            { for (int i = j+1; i < j+d  i <= N; i++)
              if (a[pq[j]] > a[pq[i]]) j = i;
              if (!(a[pq[k]] > a[pq[j]])) break;
              exch(k, j); k = j;
            }
        }
    public:
      PQi(int N, const vector<keyType> a, int d = 3) :
        a(a), pq(N+1, 0), qp(N+1, 0), N(0), d(d) { }
      int empty() const { return N == 0; }
      void insert(int v)
        { pq[ + +N] = v; qp[v] = N; fixUp(N); }
      int getmin()
        { exch(1, N); fixDown(1, N-1); return pq[N--]; }
      void lower(int k)
        { fixUp(qp[k]); }
    };
      

Использование пирамидальных d-деревьев неэффективно для разреженных графов, поскольку d должно быть целым числом, большим или равным 2, из чего следует, что мы не можем получить асимптотическое время выполнения меньше VlgV. Если плотность графа принимает небольшое постоянное значение, то линейный по времени алгоритм вычисления MST будет выполняться за время, пропорциональное V.

Цель разработки практических алгоритмов вычисления MST для разреженных графов за линейное время все еще не достигнута. Интенсивно изучались различные варианты алгоритма Борувки как основы для алгоритмов вычисления MST для сильно разреженных графов за почти линейное время (см. раздел ссылок). Такие исследования позволяют надеяться на получение в будущем линейного по времени алгоритма, пригодного для практических целей; было даже доказано существование рандомизированного линейного по времени алгоритма. Такие алгоритмы обычно довольно сложны, но упрощенные версии некоторых из них могут оказаться вполне работоспособными. А пока в большинстве практических ситуаций мы можем использовать рассмотренные здесь базовые алгоритмы для вычисления MST-дерева за линейное время — возможно, с дополнительным множителем lgV для некоторых разреженных графов.

Упражнения

20.71.[ В. Высоцкий] Разработайте реализацию алгоритма, описанного в разделе 20.2, который строит MST, добавляя в него ребра по одному за раз и удаляя самые длинные ребра из образующихся циклов (см. упражнение 20.33). Воспользуйтесь представлением леса MST-поддеревьев в виде родительских ссылок. Указание. При обходе путей в деревьях меняйте направления указателей на обратные.

20.72. Эмпирически сравните время выполнения реализации из упражнения 20.71 и времени выполнения алгоритма Крускала для различных видов взвешенных графах (см. упражнения 20.9—20.14). Проверьте, влияет ли на результаты рандомизация порядка просмотра ребер.

20.73. Опишите, как можно найти MST для такого большого графа, что в памяти одновременно могут находиться лишь V ребер.

20.74. Разработайте реализацию очереди с приоритетами, в которой операции извлечь минимальное и найти минимальное выполняются за постоянное время, а время выполнения операции уменьшить ключ пропорционально логарифму размера очереди с приоритетами. Сравните полученную реализацию с пирамидальными 4-деревьями, когда для вычисления MST-дерева разреженных графов используется алгоритм Прима, для различных видов взвешенных графов (см. упражнения 20.9—20.14).

20.75. Эмпирически сравните производительность различных реализаций очереди с приоритетами при использовании алгоритма Прима для различных видов взвешенных графов (см. упражнения 20.9—20.14). Рассмотрите пирамидальные d-деревья для различных значений d, биномиальные очереди, контейнер priority_queue из библиотеки STL, сбалансированные деревья и любые другие структуры данных, которые вы сочтете эффективными.

20.75. Разработайте реализацию, которая позволяет использовать в алгоритме Борувки обобщенную очередь, содержащую лес MST-поддеревьев. (Применение программы 20.9 соответствует использованию очереди FIFO.) Поэкспериментируйте с другими реализациями обобщенных очередей для различных видов взвешенных графов (см. упражнения 20.9—20.14).

20.77. Разработайте генератор случайных связных кубических графов (каждая вершина которого имеет степень 3) с ребрами случайных весов. Подстройте рассмотренные нами алгоритмы вычисления MST для этого случая, а затем определите, какой из них работает быстрее.

20.78. Для V = 106 начертите график зависимости отношения верхней границы трудоемкости алгоритма Прима с пирамидальным d-деревом к E от насыщенности d, для а из диапазона от 1 до 100.

20.79. Из таблицы 20.2 следует, что стандартная реализация алгоритма Крускала работает значительно быстрее, чем реализация с частичным упорядочением, для графов малой плотности. Объясните это явление.

20.80. Эмпирически определите в стиле таблицы 20.2 результаты для случайных полных графов с нормально распределенными весами (см. упражнение 20.18).

Евклидово MST-дерево

Пусть даны N точек на плоскости, и нужно найти кратчайшее множество линий, соединяющих все эти точки. Эта геометрическая задача называется задачей поиска евклидова MST-дерева (Euclidian MST) (см. рис 20.18). Один из способов ее решения — построение полного графа с N вершинами и N(N — 1)/2 ребрами — каждую пару вершин соединяет одно ребро, а вес этого ребра равен расстоянию между его вершинами. Затем при помощи алгоритма Прима можно найти MST-дерево за время, пропорциональное N².

Обычно это решение работает слишком медленно. Евклидова задача несколько отличается от задач на графах, которые мы рассматривали выше: в ней все ребра определены неявно. Объем входных данных пропорционален N, так что наш первый вариант решения этой задачи является квадратичным. Исследования показывают, что возможны лучшие решения. Геометрическая структура подразумевает, что большая часть ребер полного графа не понадобится при решении задачи, и большая часть этих ребер не нужна для построения минимального остовного дерева.

Евклидово MST-дерево для заданного множества N точек на плоскости (вверху) — это кратчайшее множество соединяющих их линий (внизу). Эта задача выходит за рамки задач обработки графов, поскольку для ее решения необходимо использовать глобальную геометрическую информацию о точках на плоскости, чтобы не обрабатывать все N² неявных ребер, соединяющих эти точки.

В принципе, триангуляцию Делоне можно вычислить за время, пропорциональное N logN, а затем вычислить евклидово MST-дерево за время, пропорциональное N logN, с помощью либо алгоритма Крускала, либо метода поиска по приоритету. Однако написание программы вычисления триангуляции Делоне — задача не из легких даже для опытного программиста, поэтому на практике такой подход может оказаться слишком трудным для решения подобных задач.

Другие подходы вытекают из геометрических алгоритмов, которые будут рассматриваться в части 7. Для случайно распределенных точек можно поделить плоскость на квадраты таким образом, чтобы каждый квадрат содержал примерно , 20.13, 20.16 и других подобных рисунках, были построены с использованием именно так (рис 20.19). А можно разработать специальную версию алгоритма Прима с использованием алгоритмов поиска ближайшего соседа, чтобы не обрабатывать дальние вершины.

Имея такой набор инструментов и возможности линейных алгоритмов для решения общей задачи вычисления MST, важно помнить о существовании простой нижней границы наших возможностей.

Один из способов вычисления евклидова MST-дерева состоит в построении графа, ребра которого соединяют каждую пару точек, расположенных друг от друга на расстоянии, не превышающем d, подобно графу на рис 20.8 и т.д. Однако при слишком больших d этот метод дает слишком много ребер (вверху), а если d меньше длины самого длинного ребра в MST, то нельзя гарантировать, что будут доступны все нужные ребра (внизу).

Точные интерпретации этой нижней границы довольно сложны, поскольку базовые операции, используемые для решения этих двух задач (сравнение координат в задаче сортировки и сравнение расстояний в задаче построения MST), различны и поскольку можно использовать методы наподобие поразрядной сортировки и решеточных методов. Однако можно интерпретировать эту границу так: при выполнении сортировки следует считать алгоритм вычисления евклидова MST-дерева с NlgN операциями сравнения оптимальным, если не использовать числовые свойства координат — в этом случае можно надеяться на линейное время выполнения (см. раздел ссылок).

Существует интересная связь между графами и геометрическими алгоритмами, которая вытекает из задачи вычисления евклидова MST-дерева. Многие задачи, которые часто встречаются на практике, могут быть сформулированы либо как геометрические задачи, либо как задачи на графах. Если важно физическое расположение объектов, то можно пользоваться геометрическими алгоритмами, описанными в части VII; но если важнее взаимосвязи между объектами, то обычно удобнее алгоритмы на графах, рассмотренные в данном разделе.

Евклидово MST-дерево находится примерно посередине между двумя этими подходами (на входе геометрические данные, а на выходе — взаимосвязи), и поэтому разработка простых методов вычисления евклидова MST-дерева остается трудной задачей. В мы столкнемся с еще одной подобной задачей, которая также находится в этом промежутке, но там евклидов подход допускает гораздо более быстрые алгоритмы, чем соответствующие задачи на графах.

Упражнения

20.81. Приведите контрпример, показывающий, почему не работает следующий метод поиска евклидова MST-дерева: " Упорядочьте точки по их координатам х, потом найдите минимальные основные деревья для первой половины и для второй половины, а затем найдите соединяющие их кратчайшие ребра " .

20.82. Разработайте быструю версию алгоритма Прима для вычисления евклидова MST-дерева для множества равномерно распределенных случайных точек на плоскости, которая основана на игнорировании отдаленных точек до тех пор, пока к ним не приблизится само дерево.

20.83. Разработайте алгоритм, который для заданного множества N точек на плоскости находит множество ребер с мощностью, пропорциональной N, которое наверняка содержит MST и которое достаточно просто вычисляется, чтобы разработать компактную и эффективную реализацию алгоритма.

20.84. Пусть дано множество случайных N точек, равномерно распределенных в единичном квадрате. Эмпирически определите с точностью до двух десятичных цифр значение d, такое, что множество ребер, образованных всеми парами точек на расстоянии не более d, содержит MST с вероятностью 99%.

20.85. Выполните упражнение 20.84 для точек, каждая координата которых получена из гауссова распределения со средним значением 0.5 и со среднеквадратичным отклонением 0.1.

20.86. Опишите, как можно повысить производительность алгоритмов Крускала и Борувки для случая разреженных евклидовых графов.