Содержание
-
Построение минимального остовного дерева.Алгоритм Краскала
Подготовила ученица 10-А класса ЭМЛ Огурцова Валерия
-
1 2 7 3 6 5 4 5 15 7 5 5 5 5 5 3 1 25 15 Таблица смежности данного графа Дан взвешенный граф
-
1 2 7 3 6 5 4 5 15 7 5 5 5 5 5 3 1 25 15 В алгоритме Краскала рассматриваются не вершины, а ребра. Идеей этого метода есть постепенное построение остовного дерева за счет соединения отдельных поддеревьев в единое. Сначала в пустое остовное дерево записывается ребро с наименьшим весом. Дальше делаем аналогично, т.е. добавляем ребра с наименьшим весом, которые ещё не были записаны в остовное дерево.
-
Алгоритм можно сформулировать так: 1. Определяем начально состояние остовного дерева как пустой и считаем, что все вершины создают N поддеревьев, которые в свою очередь не имеют никаких ребер. Присвоим им имена порядкового номера соответствующих вершин. 2. Если же количество ребер в остовном дереве меньше чем (N-1), то среди свободных ребер данного графа, которые ещё не были задействованы в остовном дереве, определяем ребро с наименьшим весом. Таки ребром может быть ребро, которое принадлежит разным поддеревьям. В другом случаи переходи к пункту 4. 3. Добавляем новое ребро к остовному дереву, а вершинам, которые принадлежат двум поддеревьям, что объединяются, и к оторым принадлежат вершины текущего ребра, присвоить значение порядкового номера одного из поддеревьев. 4. Завершить алгоритм.
-
1 2 7 3 6 5 4 5 15 7 5 5 5 5 5 3 1 25 15 1 2 3 4 5 6 7 1 2 7 3 6 5 4 1 2 3 4 5 6 7 1. Находим ребро с наименьшим весом. В нашем случае это ребро (4,6). И заносим его в массив.
-
Дальше мы ищем ребра с наименьшим весом, и действуем аналогично. 1 2 7 3 6 5 4 5 15 7 5 5 5 5 5 3 1 25 15 1 2 3 4 5 6 7 1 2 7 3 6 5 4 1 2 3 4 5 6 7 1 (4,6) 3 (5,6) 5 5 5 7 1 3 5 (1,2) 5 (3,4) 5 (3,7) 7 (2,7)
-
Надеемся вы поняли, как работает этот алгоритм. СПАСИБО ЗА ВНИМАНИЕ!
Нет комментариев для данной презентации
Помогите другим пользователям — будьте первым, кто поделится своим мнением об этой презентации.