Глава 20. Минимальные остовные деревья. MST (const Graph &G) : G(G),

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(); } };

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

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

Часть 5. Алгоритмы на графах

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

Свойство 20.7. Использование реализации алгоритма Прима с поиском по приоритету, в котором для реализации очереди с приоритетами применяется полное бинарное дерево, по­зволяет вычислить дерево MST за время, пропорциональное Е IgV

Доказательство: Этот алгоритм напрямую реализует обобщенную идею алгоритма При­ма (добавлять в дерево MST в качестве очередного минимальное ребро, которое со­единяет некоторую вершину MST с вершиной, не входящей в MST). Каждая опера­ция для очереди с приоритетами требует выполнения действий, число которых не превосходит значения lgV Каждая вершина выбирается при помощи операции удалить минимальное ребро (remove the minimum); при этом в худшем случае каждое ребро мо­жет потребовать выполнения операции изменить приоритет (change priority). ■

Поиск по приоритету представляет собой подходящее обобщение поиска ширину и поиска в глубину, ибо эти методы также могут быть получены за счет соответствующего выбора установок. Например, мы можем (в какой-то степени искусственно) использо­вать переменную cnt для присвоения уникального приоритета cnt++ каждой вершине, когда помещаем ее в очередь по приоритетам. Если мы определим, что Р есть cnt, мы получаем нумерацию узлов при обходе в прямом порядке и поиск в глубину, поскольку вновь встреченные узлы имеют наивысший приоритет. Если мы определим, что Р есть V-cnt, мы получаем поиск в ширину, поскольку наивысший приоритет в этом случае име­ют старые узлы. Присвоение таких значений приоритетов приводят к тому, что очереди с приоритетами ведут себя, соответственно, как стеки и как собственно очереди. Такая эквивалентность представляет чисто академический интерес, поскольку операции на очередях по приоритету не обязательны для поиска в глубину и для поиска в ширину. Кроме того, как уже отмечалось в разделе 18.8, формальное доказательство эквивалент­ности требует строгого соблюдения правила замены, чтобы получить ту же последователь­ность вершин как результат выполнения классических алгоритмов.

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

Свойство 20.8. Для всех графов и приоритетных функций можно вычислить остовное де­рево при помощи поиска по приоритетам за линейное время плюс время, пропорциональное продолжительности выполнения V операций вставок (insert), V операций удалить мини­мальное ребро (delete the minimum) и Е операций уменьшить ключ (decrease key) в очере­ди с приоритетами, размер которой не превышает V.

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

Доказательство: Доказательство свойства 20.7 устанавли­вает этот результат в более общей форме. Мы должны проверить все ребра графа; отсюда следует условие " ли­нейного времени". Рассматриваемый алгоритм никогда не увеличивает приоритет (он изменяет приоритет в сто­рону уменьшения). За счет более точного описания того, что нам нужно от АТД очереди с приоритетами (умень­шить ключ, а не обязательно изменить приоритет), мы усиливаем формулировку требований к рабочим харак­теристикам алгоритма. ■

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

Свойство 20.7 представляет собой важный общий резуль­тат: устанавливаемая им временная граница есть верхняя граница для худшего случая, которая гарантирует для широ­кого класса задач обработки графов производительность, отличающуюся от оптимальной (линейное время) не более чем в lgV paз. Однако существуют две причины, в силу ко­торых оно дает в некотором смысле пессимистическую оценку производительности на многих видах графов, с ко­торыми нам приходится сталкиваться на практике. Во-пер­вых, граница lgМ для операций с очередями с приоритета­ми сохраняется только в тех случаях, когда количество вершин в бахроме пропорционально V, и даже в таком слу­чае это всего лишь верхняя граница. В случае реального фа-фа из практического приложения бахрома может быть не­большим множеством (см. рис. 20.10 и 20.11), а на выполнение реализаций некоторых операций на очереди с приоритетами будет затрачено существенно меньше, чем l gV действий. Хотя этот эффект и заметен, тем не менее он оп­ределяет только небольшую составляющую постоянного ко­эффициента, на который умножается время выполнения; например, доказательство того, что множество составных ребер не может содержать более √ V вершин улучшит гра­ничное значение всего лишь в два раза. Что еще более важ­но, в общем случае мы выполняем намного меньше, чем E,

РИСУНОК 20.10. РЕАЛИЗАЦИЯ АЛГОРИТМА ПРИМА, ОБЕСПЕЧИВАЮЩЕГО ПОСТРОЕНИЕ ДЕРЕВА MST С ИСПОЛЬЗОВАНИЕМ ПОИСКА ПО ПРИОРИТЕТАМ. Используя поиск по приорите­там, алгоритм Прима выполняет обработку вершин и ребер, наиболее близких к дереву МST (показаны серым цветом).

Часть 5. Алгоритмы на графах

операций уменьшить ключ, поскольку мы выполняем эту операцию, только когда находим ребро, ведущее в узел, содержащийся в бахроме, которое короче из­вестного на текущий момент ребра такого же типа. Такое событие происходит довольно редко: большая часть ребер не оказывает на очередь с приоритетами никакого влияния (см. упражнение 20.40), Целесооб­разно в большинстве случаев рассматривать поиск по приоритету как линейный по времени выполнения алго­ритм при условии, что V lgV значительно больше Е.

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

Реализация дерева MTS для насыщенных графов, которая фактически эквивалентна программе 20.6, была впервые опубликована Примом (Prim) в 1961 г. и, независимо от него, Дейкстрой (Dijkstra) - не­сколько позже. Обычно она называется алгоритмом

РИСУНОК 20.11. РАЗМЕР МНОЖЕСТВА СОСТАВНЫХ РЕБЕР В УСЛОВИЯХ РЕАЛИЗАЦИИ АЛГОРИТМА ПРИМА, ИСПОЛЬЗУЮЩЕГО ПОИСК ПО ПРИОРИТЕТАМ.

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

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

20.6, с тех пор многие исследователи направили свои усилия на поиск эффективных ре­ализаций как ключевого момента отыскания эффективных алгоритмов построения дере­вьев MTS для разреженных графов.