Состав сооружений: решетки и песколовки: Решетки – это первое устройство в схеме очистных сооружений. Они представляют...
Наброски и зарисовки растений, плодов, цветов: Освоить конструктивное построение структуры дерева через зарисовки отдельных деревьев, группы деревьев...
Топ:
Оценка эффективности инструментов коммуникационной политики: Внешние коммуникации - обмен информацией между организацией и её внешней средой...
Эволюция кровеносной системы позвоночных животных: Биологическая эволюция – необратимый процесс исторического развития живой природы...
Комплексной системы оценки состояния охраны труда на производственном объекте (КСОТ-П): Цели и задачи Комплексной системы оценки состояния охраны труда и определению факторов рисков по охране труда...
Интересное:
Как мы говорим и как мы слушаем: общение можно сравнить с огромным зонтиком, под которым скрыто все...
Берегоукрепление оползневых склонов: На прибрежных склонах основной причиной развития оползневых процессов является подмыв водами рек естественных склонов...
Финансовый рынок и его значение в управлении денежными потоками на современном этапе: любому предприятию для расширения производства и увеличения прибыли нужны...
Дисциплины:
2018-01-05 | 133 |
5.00
из
|
Заказать работу |
|
|
Минимальным остовным деревом (МОД) связного взвешенного графа называется его связный подграф, состоящий из всех вершин исходного графа и некоторых его ребер, причем сумма весов ребер является минимально возможной. Такое дерево может понадобиться, например, для организации компьютерной сети.
Алгоритм Дейкстры-Прима
Дейкстра и Прим предложили так называемый «жадный» алгоритм построения МОД. «Жадные» алгоритмы действуют, используя в каждый момент часть исходных данных и принимая лучшее решение на основе этой части. В рассматриваемом случае на каждом шаге имеется множество ребер, которые могут быть присоединены к уже построенной части остовного дерева, из них выбирается ребро с наименьшим весом. Вершины графа разбиваются на три класса: вершины, вошедшие в уже построенную часть дерева, вершины, окаймляющие построенную часть, и еще не рассмотренные вершины. Алгоритм начинает работу с произвольной вершины графа, которая включается в остовное дерево. Все вершины, соединенные (соседние) с данной, заносятся в кайму. Затем выполняется цикл поиска ребра с наименьшим весом, соединяющего уже построенную часть остовного дерева с каймой; это ребро вместе с новой вершиной добавляется в дерево и происходит обновление каймы таким образом, чтобы список ребер из дерева в кайму включал ребра с наименьшими весами. После того, как в дерево попадут все вершины, работа будет закончена. Словесный алгоритм приведен ниже:
Шаг 1. Выбрать начальный узел
Шаг 2. Сформировать начальную кайму, состоящую из вершин, соседних с начальным узлом
Шаг 3. В графе есть вершины, не попавшие в дерево?
Если да, то переход на Шаг 4.
Иначе – переход на Шаг 9.
|
Шаг 4. Выбрать ребро из дерева в кайму с наименьшим весом
Шаг 5. Добавить конец ребра к дереву
Шаг 6. Изменить кайму, для чего добавить в кайму вершины, соседние с новой
Шаг 7. Обновить список ребер из дерева в кайму так, чтобы он состоял из ребер наименьшего веса
Шаг 8. Переход на Шаг 3
Шаг 9. Конец
На Рис. 3.6 изображен исходный граф:
Рис. 3.6. Исходный граф
Рис. 3.7. Добавление первой вершины. Пунктиры ведут к вершинам каймы
Рис. 3.8. Добавление второй и третьей вершин
Рис. 3.9. Добавление четвертой и пятой вершин
Рис. 3.10. Заключительные шаги алгоритма Дейкстры-Прима
Алгоритм Крускала
Другой алгоритм построения МОД предложил Крускал. Алгоритм начинает работу с пустого дерева. К нему добавляются ребра в порядке возрастания их весов до тех пор, пока не будет получен набор ребер, объединяющий все вершины графа. В процессе выполнения необходимо не допускать добавление ребер, приводящих к появлению цикла в создаваемом дереве. Если ребра закончатся до того, как все вершины будут соединены между собой, это означает, что граф был несвязным, и полученный результат представляет собой объединение МОД всех его компонент связности. Пример алгоритма приведен ниже:
1. Отсортировать ребра в порядке возрастания весов
2. Инициализировать структуру разбиений
edgeCount=l
while edgeCount<=E and includedCount<=N-l do
parentl=FindRoot(edge[edgeCount].start)
parent2=FindRoot(edge[edgeCount].end)
if parentl/=parent2 then
добавить edge[edgeCount] в остовное дерево
includedCount=includedCount+l
Union(parent1,parent2)
end if
edgeCount=edgeCount+l
end while
Для иллюстрации действия алгоритма будем использовать граф, приведенный на Рис. 3.6.
Рис. 3.11. Добавление первого ребра
Рис. 3.12. Добавление второго и третьего ребра
Рис. 3.13. Добавление четвертого и пятого ребер
Рис. 3.14. Заключительные шаги алгоритма Крускала
|
|
Опора деревянной одностоечной и способы укрепление угловых опор: Опоры ВЛ - конструкции, предназначенные для поддерживания проводов на необходимой высоте над землей, водой...
Эмиссия газов от очистных сооружений канализации: В последние годы внимание мирового сообщества сосредоточено на экологических проблемах...
Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни...
Организация стока поверхностных вод: Наибольшее количество влаги на земном шаре испаряется с поверхности морей и океанов (88‰)...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!