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

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

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

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

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

5 Находим ребро с наименьшим весом. В нашем случае это ребро (4,6). И заносим его в массив. 1- Вес ребра (4,6)- Само ребро

6 Дальше мы ищем ребра с наименьшим весом, и действуем аналогично (4,6) 3 (5,6) (1,2) 5 (3,4) 5 (3,7) 7 (2,7)

7 Надеемся вы поняли, как работает этот алгоритм. СПАСИБО ЗА ВНИМАНИЕ!