Презентация на тему "Минимальные остовные деревья. Алгоритмы Крускала и Прима"

Презентация: Минимальные остовные деревья. Алгоритмы Крускала и Прима
Включить эффекты
1 из 13
Ваша оценка презентации
Оцените презентацию по шкале от 1 до 5 баллов
  • 1
  • 2
  • 3
  • 4
  • 5
4.0
1 оценка

Комментарии

Нет комментариев для данной презентации

Помогите другим пользователям — будьте первым, кто поделится своим мнением об этой презентации.


Добавить свой комментарий

Аннотация к презентации

Интересует тема "Минимальные остовные деревья. Алгоритмы Крускала и Прима"? Лучшая powerpoint презентация на эту тему представлена здесь! Данная презентация состоит из 13 слайдов. Средняя оценка: 4.0 балла из 5. Также представлены другие презентации по информатике для студентов. Скачивайте бесплатно.

Содержание

  • Презентация: Минимальные остовные деревья. Алгоритмы Крускала и Прима
    Слайд 1

    Минимальные остовные деревья. Алгоритмы Крускала и Прима.

    Работу выполнил Студент группы И-2-10 Бекиров Алим

  • Слайд 2

    Минимальные остовные деревья

    Задача: в процессе разработке электронных схем необходимо получит такую компоновку из n-1 проводов, которая использует минимальное количество провода. Дан некий связный неориентированный граф G=(V,E), где V- множество контактов, Е- множество возможных соединений между парами контактов, и для каждого ребра (u,v)ЭЕ задан вес w(u,v), определяющий стоимость ( количество необходимого провода)соединения u и v.

  • Слайд 3

    Необходимо найти ациклическое подмножество T , которое соединяет все вершины и чей общий вес минимален. Остовным деревом(spanning tree)- называетсямножество Т, которое ациклично и связывает все вершины, при этом данное дерево имеет минимальный вес. Задачей поиска минимального остовного дерева (minimum spanning tree problem)называют задачей поиска дерева Т.

  • Слайд 4
  • Слайд 5

    Алгоритм Крускала

    Алгоритм Крускала предназначен для нахождения безопасного ребра для добавления в растущий лес путем поиска ребра (u,v) с минимальным весом среди всех ребер, соединяющий два дерева в лесу. Данный алгоритм является жадным, поскольку на каждом шаге он добавляет к лесу ребро с минимально возможным весом. Время работы алгоритма O(E lg V).

  • Слайд 6
  • Слайд 7
  • Слайд 8
  • Слайд 9

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

    Аналогично алгоритму Крускала. Построение дерева начинается с произвольной корневой вершиной r и растет до тех пор пока не охватит все вершины в V. На каждом шаге к дереву А добавляется легкое ребро, соединяющие дерево и отдельную вершину из оставшейся части графа. Время работы алгоритма O(E+ V lg V).

  • Слайд 10
  • Слайд 11
  • Слайд 12
  • Слайд 13

    Спасибо за внимание!

Посмотреть все слайды

Сообщить об ошибке