11.12. алгоритм построения деревьев
11.12. алгоритм построения деревьев
Пусть имеется некоторый граф G и каждому его ребру (х, у) поставлено в соответствие число т(х, у), которое называется его весом. Вес дерева определяется как сумма весов составляющих его ребер. Для графа G необходимо построить покрывающее дерево минимального веса.
Алгоритм построения минимального покрывающего дерева. Просматривают ребра графа G в порядке возрастания их весов. Если ребро включается в покрывающее дерево, то его окрашивают в голубой цвет, если не включается—в оранжевый. Ребра, включенные в дерево, образуют граф, состоящий из нескольких компонент. Если концевые вершины просматриваемого ребра принадлежат одной и той же компоненте, то ребро образует цикл с ребрами, ранее включенными в дерево. Такое ребро не включают в дерево. Если же концевые вершины не принадлежат одной компоненте, то ребро включают в дерево. Вершины одной связной компоненты составляют букет.
1. Берут любое ребро, не являющееся петлей. Окрашивают его в голубой цвет, а его концевые вершины включают в первый букет.
323
Выбирают неокрашенное ребро и окрашивают его:
а) в оранжевый цвет, если концевые вершины ребра принадлежат одному и тому же букету;
б) в голубой цвет, если:
концевые вершины не принадлежат ни одному из букетов (в этом случае вершины включают в новый букет);
концевые вершины принадлежат разным букетам (в этом случае эти букеты объединяют в один);
один конец ребра принадлежит некоторому букету, а второй не входит ни в один букет (в этом случае второй конец включают в тот же букет).
Заканчивают процедуру, если все вершины графа вошли в один букет. В противном случае переходят в шагу 2.
Число шагов при выполнении алгоритма конечно, так как оно не превышает числа ребер графа. Если голубые ребра не образуют покрывающего дерева, то у исходного графа его нет.
О Пример. В новом районе имеется шесть жилых массивов. Нужно соединить их между собой дорогами, стоимость прокладки которых была бы минимальна. В таблице приведена стоимость постройки дорог между каждой парой жилых массивов:
Рис. 11.22
Построено покрывающее дерево, вес которого равен 25 (рис. 11.22). •
Обсуждение Справочник по математике для экономистов
Комментарии, рецензии и отзывы