Часть 5. Алгоритмы на графах. и мы исследуем их в этом разделе несколько позже, после того как рассмотрим реали­зации более подробно.

и мы исследуем их в этом разделе несколько позже, после того как рассмотрим реали­зации более подробно.

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

■ Вычисление потенциалов вершин.

■ Наращивание потока в циклах (и выявление на нем порожних или заполненных
ребер).

■ Вставка нового ребра и удаление ребра из образованного при этом цикла.

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

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

Программа 22.10 представляет реализацию, которая присваивает потенциалы верши­нам за время, пропорциональное V. В ее основе лежит следующая идея, проиллюстриро­ванная на рис. 22.47. Мы начинаем с того, что выбираем любую вершину и в рекурсив­ном режиме вычисляем потенциалы ее предшественников, следуя вверх по родительскому списку до самого корня, которому по соглашению присваивается потенциал 0. Затем мы выбираем другую вершину и используем родительские связи для рекурсивного вычисле­ния потенциалов ее предшественников. Рекурсивные вычисления заканчиваются, когда мы достигнем предшественника, потенциал которого известен; далее, при выходе из ре­курсии мы возвращаемся по тому же пути, вычисляя потенциал каждого узла с исполь­зованием потенциала родителя. Процесс продолжается до тех пор, пока не будут вычис­лены значения потенциалов. Если мы уже прошли по какому-либо пути, то мы больше не посещаем ни одно из его ребер, следовательно, этот процесс протекает в течение вре­мени, пропорционального числу вершин V.

Программа 22.10. Вычисление потенциала вершины______________________________

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