Часть 5. Алгоритмы на графах. На рис. 20.8 показан пример построения дерева MST с помощью алгоритма Прима; на рис

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

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

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

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

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

Реализация алгоритма Прима представляет собой метод, которому отдается предпочтение при работе с насыщенными графами и который может быть использовано для любого представления графа, поддерживающее функцию edge, выполняющую проверку существования заданного ребра. Внешний цикл обеспечивает приращение дерева 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;