Студопедия Главная Случайная страница Обратная связь

Разделы: Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Алгоритм Прима





Алгоритм предназначен для построения минимального остовного дерева графа G.

Шаги:

1. Рассчитываются длины всех ребер графа, являющегося моделью исходного описания объекта.

2. Ребра ранжируются в порядке возрастания длины.

3. Из ребер, инцидентных вершинам построенного фрагмента дерева, выбирается ребро, имеющее минимальную длину и не образующего цикла с ребрами, уже включенными в дерево. На первом шаге выбирается ребро минимальной длины. Процесс заканчивается, когда все вершины соединены ребрами.

 

Общий вид работы алгоритма показан на рисунке слева. На нем использованы следующие условные обозначения:

-множество вариантов, содержащих ребро .

- множество вариантов, НЕ содержащих ребро .

И так далее.

 

 

 

 







Дата добавления: 2015-04-19; просмотров: 469. Нарушение авторских прав; Мы поможем в написании вашей работы!




Композиция из абстрактных геометрических фигур Данная композиция состоит из линий, штриховки, абстрактных геометрических форм...


Важнейшие способы обработки и анализа рядов динамики Не во всех случаях эмпирические данные рядов динамики позволяют определить тенденцию изменения явления во времени...


ТЕОРЕТИЧЕСКАЯ МЕХАНИКА Статика является частью теоретической механики, изучающей условия, при ко­торых тело находится под действием заданной системы сил...


Теория усилителей. Схема Основная масса современных аналоговых и аналого-цифровых электронных устройств выполняется на специализированных микросхемах...

Виды нарушений опорно-двигательного аппарата у детей В общеупотребительном значении нарушение опорно-двигательного аппарата (ОДА) идентифицируется с нарушениями двигательных функций и определенными органическими поражениями (дефектами)...

Особенности массовой коммуникации Развитие средств связи и информации привело к возникновению явления массовой коммуникации...

Тема: Изучение приспособленности организмов к среде обитания Цель:выяснить механизм образования приспособлений к среде обитания и их относительный характер, сделать вывод о том, что приспособленность – результат действия естественного отбора...

Виды и жанры театрализованных представлений   Проживание бронируется и оплачивается слушателями самостоятельно...

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

Реостаты и резисторы силовой цепи. Реостаты и резисторы силовой цепи. Резисторы и реостаты предназначены для ограничения тока в электрических цепях. В зависимости от назначения различают пусковые...

Studopedia.info - Студопедия - 2014-2025 год . (0.012 сек.) русская версия | украинская версия