11.12. алгоритм построения деревьев

11.12. алгоритм построения деревьев

Пусть имеется некоторый граф G и каждому его ребру (х, у) поставлено в соответствие число т{х, у), которое называется его весом.

Вес дерева определяется как сумма весов составляющих его ребер. Для графа G необходимо построить покрывающее дерево минимального веса.

Алгоритм построения минимального покрывающего дерева

Просматривают ребра графа G в порядке возрастания их весов. Если ребро включается в покрывающее дерево, то его окрашивают в голубой цвет, в противном случае — в оранжевый цвет. Ребра, включенные в дерево, образуют граф, состоящий из нескольких компонент. Если концевые вершины просматриваемого ребра принадлежат одной и той же компоненте, то ребро образует цикл с ребрами, ранее включенными в дерево. Такое ребро не включают в дерево. В противном случае ребро включают в дерево. Вершины одной связной компоненты составляют букет.

Берут любое ребро, не являющееся петлей. Окрашивают его в голубой цвет, а его концевые вершины включают в первый букет.

Выбирают неокрашенное ребро.

Если его концевые вершины принадлежат одному и тому же букету, то окрашивают ребро в оранжевый цвет.

Если ни одна из его концевых вершин не принадлежит ни одному из букетов, то включают их в новый букет и окрашивают ребро в голубой цвет.

Если концевые вершины принадлежат разным букетами, то объединяют эти букеты в один и окрашивают ребро в голубой цвет.

Если один конец ребра принадлежит некоторому букету, а второй не входит ни в один букет, то нужно включить второй конец в тот же букет и окрасить ребро в голубой цвет.

Заканчивают процедуру, если все вершины графа вошли в один букет. В противном случае переходят в шагу 2.

Число шагов при выполнении алгоритма конечно, так как оно не превышает числа ребер графа. Если голубые ребра не образуют покрывающего дерева, то у исходного графа его нет.

О Пример. В новом районе имеется шесть жилых массивов. Нужно соединить их между собой дорогами, стоимость прокладки которых была бы минимальна. В следующей таблице приведены стоимости постройки дорог между каждой парой жилых массивов:

Построено покрывающее дерево, вес которого равен 25 (рис. 11.22). •