![]() Главная страница Случайная страница КАТЕГОРИИ: АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
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]; } } } };
Доказательство: Поскольку число деревьев в лесе уменьшается наполовину на каждом этапе, число этапов непревышает значения 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.
|