Программа 20.9. Алгоритм Борувки построения дерева MTS

Эта реализация алгоритма Борувки построения дерева MTS использует версию АТД объединения-поиска из главы 4 (в интерфейс добавляется функция find с одним аргументом) с целью привязки индексов к поддеревьям MTS по мере их построения. На каждом этапе проверяются все оставшиеся ребра; те из них, которые соединяют отдельные поддеревья, сохраняются до следующего этапа. Массив а содержит ребра, которые не были отвергнуты и которые еще не включены в поддеревья MTS. Индекс N используется для хранения ребер, отложенных до следующего этапа (приводимый ниже программный код переустанавливает значение Е вместо N в конце каждого этапа), а индекс h используется для доступа к следующему проверяемому ребру. Ближайший сосед каждой компоненты хранится в массиве b с номерами компоненты find в качестве индексов. В конце каждого этапа каждая компонента соединяется с ближайшей соседней, а ребра ближайшей соседней вершины добавляются в дерево MTS.

РИСУНОК 20.14. АЛГОРИТМ БОРУВКИ ПОСТРОЕНИЯ ДЕРЕВА MTS

На диаграмме вверху показаны ориентированные ребра, проведенные из каждой вершины в ближайшие к ним соседние вершины. Ив этой диаграммы следует, что ребра 0-2, 1-7 и 3-5 являются самыми короткими ребрами, инцидентные обоим их вершинам, 6-7 есть кратчайшее ребро для вершины б, а 4-3 — кратчайшее ребро для вершины 4. Все эти ребра содержатся в дереве MTS и образуют лес поддеревьев MTS (диаграмма в центре), который вычисляется на первом этапе выполнения алгоритма Борувки. На втором этапе этот алгоритм завершает вычисление поддеревьев MTS (диаграмма внизу) добавлением ребра 0-7, которое является кратчайшим ребром, инци­дентным каждой вершине тех поддеревьев, которые он соединяет между собой, и ребра 4- 7, которое является кратчайшим ребром, инци­дентным каждой вершине нижнего поддерева.

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

template < с1азз Graph, class Edge> class MST { const Graph & G;

vector< Edge *> a, b, mst; UF uf; public:

MST (const Graph & G): G(G), uf(G.V()), mst(G.V<)+l) {a = edges< Graph, Edge> (G); int N, к «1;

for (int E = a.size(); E! = 0; E = N) { int h, i, j;