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] m 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. Время прогона алгоритма Бо­рувки с целью вычисления дерева MTS заданного графа есть O(E lgV lg*E).

Доказательство: Поскольку число деревьев в лесе уменьшается наполовину на каждом этапе, число этапов непревышает значения lg V. Вре­мя выполнения каждого этапа, самое большее, пропорционально затратам на выполнение Е операций find, что меньше E lg*E, или линейно с точки зрения практических приложений. ■

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

РИСУНОК 20.15. ПРИМЕНЕНИЕ МАССИВА ПОИСКА-ОБЪЕДИНЕНИЯ В АЛГОРИТМЕ БОРУВКИ

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

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

ритм отыскивает дерево MTS приводимого нами в качестве примера более крупного графа всего лишь за четыре этапа.

Можно сдвинуть коэффициент lg*£ в область более низких теоретических границ времени прогона алгоритма Борувки и сделать его пропорциональным E lgV зa счет представления поддеревьев MTS в виде двухсвязных списков вместо исполь­зования операций union и find. Однако это усовершенствование достаточно трудно для реализации и возможное повышение производительности не настолько заметно, чтобы можно было рекомендовать его для применения в практических приложе­ниях (см. упражнения 20.66 и 20.67).

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