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-l);

РИСУНОК 20.13. АЛГОРИТМ КРУСКАЛА, ОБЕСПЕЧИВАЮЩИЙ ПОСТРОЕНИЕ ДЕРЕВА MST

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

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

for (int i = 0, к =s 1; i < E & & к < V; i++) if (! uf.find(a[i]-> v, a[i]-> w)) { uf.unite(a[i]-> v, a[i]-> w);

mst[k++] = a[i]; } } };

Свойство 20.9. Алгоритм Крускала вычисляет дерево MST графа за время, пропорциональ­ное Е lgE.

Доказательство: Это свойство является следствием более общего факта, устанавлива­ющего, что время выполнения программы 20.8 пропорционально затратам на сорти­ровку Е чисел плюс стоимость Е операций поиска (find) и V- 1 операций объединения (union). Если мы используем стандартные реализации АТД, такие как сортировка сли­янием и взвешенный алгоритм поиска-объединения с делением пополам, то основные затраты приходятся на сортировку. ■

Мы проведем сравнение производительности алгоритмов Крускала и Прима в разде­ле 20.6. А пока обратите внимание на то обстоятельство, что время выполнения, пропор­циональное E lgE, не обязательно хуже, чем E lgV, поскольку Е, самое большее, может достигать значения V², следовательно, lgE нe превосходит 21gV Различие в производи­тельности на конкретных графах обусловливаются особенностями реализации и зависят от того, приближается ли фактическое время выполнения к этим граничным значениям, соответствующим худшему случаю.

На практике мы можем воспользоваться быстрой сортировкой или быстрой систем­ной сортировкой (в основу которой, скорее всего, будет положена быстрая сортировка). И хотя следствием такого подхода может быть непривлекательная (по крайней мере, в теории) квадратичная зависимость времени выполнения сортировки в худшем случае, тем не менее, она, по-видимому, может дать максимально возможное быстродействие рас­сматриваемого алгоритма. В самом деле, с другой стороны, мы можем воспользоваться поразрядной сортировкой, чтобы выполнить упорядочение ребер за линейное время (при определенных ограничениях на веса ребер), благодаря чему затраты на выполнение Е операций find будут составлять основную часть всех затрат, и внести изменения в форму­лировку свойства 20.9, в результате чего это свойство будет утверждать, что при сохра­нении прежних требований к весам ребер время выполнения алгоритма Крускала не вы­ходит за пределы постоянного коэффициента в выражении E lgE (см. главу 2). Напомним, что функция l g*E есть число итераций двоичной логарифмической функции, прежде чем результат примет значение меньше единицы; ее значение меньше 5, если Е меньше 2⁶⁵⁵³⁶. Другими словами, такая корректировка делает алгоритм Крускала в дей­ствительности линейным в большинстве практических ситуаций.

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

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