Построение минимального остовного дерева. Алгоритм Краскала Подготовила ученица 10-А класса ЭМЛ Огурцова Валерия

Август 30, 2022

Главная
Технология
Построение минимального остовного дерева. Алгоритм Краскала Подготовила ученица 10-А класса ЭМЛ Огурцова Валерия

Содержание

2. Таблица смежности данного графа Дан взвешенный граф
3. В алгоритме Краскала рассматриваются не вершины, а ребра. Идеей этого метода есть постепенное построение остовного дерева
4. Алгоритм можно сформулировать так: 1. Определяем начально состояние остовного дерева как пустой и считаем, что все
5. 1. Находим ребро с наименьшим весом. В нашем случае это ребро (4,6). И заносим его в
6. Дальше мы ищем ребра с наименьшим весом, и действуем аналогично. 1 (4,6) 3 (5,6) 5 5
8. Скачать презентацию

Слайд 2

Таблица смежности данного графа
Дан взвешенный граф

Слайд 3

В алгоритме Краскала рассматриваются не вершины, а ребра. Идеей этого метода

есть постепенное построение остовного дерева за счет соединения отдельных поддеревьев в единое. Сначала в пустое остовное дерево записывается ребро с наименьшим весом. Дальше делаем аналогично, т.е. добавляем ребра с наименьшим весом, которые ещё не были записаны в остовное дерево.

Слайд 4

Алгоритм можно сформулировать так:
1. Определяем начально состояние остовного дерева как пустой

и считаем, что все вершины создают N поддеревьев, которые в свою очередь не имеют никаких ребер. Присвоим им имена порядкового номера соответствующих вершин.
2. Если же количество ребер в остовном дереве меньше чем (N-1), то среди свободных ребер данного графа, которые ещё не были задействованы в остовном дереве, определяем ребро с наименьшим весом. Таки ребром может быть ребро, которое принадлежит разным поддеревьям. В другом случаи переходи к пункту 4.
3. Добавляем новое ребро к остовному дереву, а вершинам, которые принадлежат двум поддеревьям, что объединяются, и к оторым принадлежат вершины текущего ребра, присвоить значение порядкового номера одного из поддеревьев.
4. Завершить алгоритм.

Слайд 5