Содержание
-
Минимальные остовные деревья. Алгоритмы Крускала и Прима.
Работу выполнил Студент группы И-2-10 Бекиров Алим
-
Минимальные остовные деревья
Задача: в процессе разработке электронных схем необходимо получит такую компоновку из n-1 проводов, которая использует минимальное количество провода. Дан некий связный неориентированный граф G=(V,E), где V- множество контактов, Е- множество возможных соединений между парами контактов, и для каждого ребра (u,v)ЭЕ задан вес w(u,v), определяющий стоимость ( количество необходимого провода)соединения u и v.
-
Необходимо найти ациклическое подмножество T , которое соединяет все вершины и чей общий вес минимален. Остовным деревом(spanning tree)- называетсямножество Т, которое ациклично и связывает все вершины, при этом данное дерево имеет минимальный вес. Задачей поиска минимального остовного дерева (minimum spanning tree problem)называют задачей поиска дерева Т.
-
-
Алгоритм Крускала
Алгоритм Крускала предназначен для нахождения безопасного ребра для добавления в растущий лес путем поиска ребра (u,v) с минимальным весом среди всех ребер, соединяющий два дерева в лесу. Данный алгоритм является жадным, поскольку на каждом шаге он добавляет к лесу ребро с минимально возможным весом. Время работы алгоритма O(E lg V).
-
-
-
-
Алгоритм Прима
Аналогично алгоритму Крускала. Построение дерева начинается с произвольной корневой вершиной r и растет до тех пор пока не охватит все вершины в V. На каждом шаге к дереву А добавляется легкое ребро, соединяющие дерево и отдельную вершину из оставшейся части графа. Время работы алгоритма O(E+ V lg V).
-
-
-
-
Спасибо за внимание!
Нет комментариев для данной презентации
Помогите другим пользователям — будьте первым, кто поделится своим мнением об этой презентации.