Россия, Казань
СДЕЛАЙТЕ СВОИ УРОКИ ЕЩЁ ЭФФЕКТИВНЕЕ, А ЖИЗНЬ СВОБОДНЕЕ
Благодаря готовым учебным материалам для работы в классе и дистанционно
Скидки до 50 % на комплекты
только до 19.05.2025
Готовые ключевые этапы урока всегда будут у вас под рукой
Организационный момент
Проверка знаний
Объяснение материала
Закрепление изученного
Итоги урока
Была в сети 12.11.2024 13:28
Халяпова Наиля Миргарифановна
Учитель информатики
1 345
44 542 
Местоположение
Специализация
Алгоритм Краскала
Категория:
Информатика
01.10.2019 23:17
Просмотр содержимого документа
«Алгоритм Краскала»
Задача.
Для взвешенного графа, заданного списком ребер, найти минимальное остовное дерево, воспользовавшись алгоритмом Краскала. (Указание: в первой и второй строках таблицы указаны концевые вершины ребер, а в третьей – веса соответствующих ребер).
| Вершины ребра | 7 | 7 | 7 | 7 | 7 | 7 | 1 | 2 | 3 | 4 | 5 | 6 | 5 | 4 | 8 |
| 1 | 2 | 3 | 4 | 5 | 6 | 2 | 3 | 4 | 5 | 6 | 1 | 8 | 9 | 9 | |
| Вес ребра | 1 | 4 | 9 | 16 | 25 | 36 | 20 | 15 | 3 | 17 | 28 | 23 | 14 | 6 | 5 |
Решение.
Определение. Минимальное остовное дерево (или минимальное покрывающее дерево) в связанном взвешенном неориентированном графе – это остовное дерево этого графа, имеющее минимальный возможный вес, где под весом дерева понимается сумма весов входящих в него рёбер.
Построим граф по таблице:
До начала работы алгоритма необходимо отсортировать рёбра по весу. После сортировки таблица примет вид:
| Вершины ребра | 7 | 3 | 7 | 8 | 4 | 7 | 5 | 2 | 7 | 4 | 1 | 6 | 7 | 5 | 7 |
| 1 | 4 | 2 | 9 | 9 | 3 | 8 | 3 | 4 | 5 | 2 | 1 | 5 | 6 | 6 | |
| Вес ребра | 1 | 3 | 4 | 5 | 6 | 9 | 14 | 15 | 16 | 17 | 20 | 23 | 25 | 28 | 36 |
Приступим к построению остовного дерева:
| Изображение | Описание |
|
| Ребро 7-1 имеет минимальный вес из всех весов ребер, равный 1. |
|
| Теперь наименьший вес, равный 3, имеет ребро 3-4. Так как добавление 3-4 не образует цикла, то выбираем его в качестве второго ребра. |
|
| Аналогично выбираем ребро 7-2, вес которого равен 4. |
|
| Далее выбираем ребро 8-9, вес которого равен 5. |
|
| Выбираем ребро 4-9, вес которого равен 6. |
|
| Выбираем ребро 7-3, вес которого равен 9. |
|
| Выбираем ребро 5-8, вес которого равен 14. |
|
| Ребро 2-3, вес которого равен 15, образует цикл 2-3-7. Его не берем в остовное дерево. Ребро 7-4, вес которого равен 16, образует цикл 7-3-4. Его не берем в остовное дерево. Ребро 4-5, вес которого равен 17, образует цикл 4-9-8-5. Его не берем в остовное дерево. Ребро 1-2, вес которого равен 20, образует цикл 1-2-7. Его не берем в остовное дерево. Выбираем ребро 6-1, вес которого равен 23. |
|
| Ребро 7-5, вес которого равен 25, образует цикл 7-3-4-9-8-5. Его не берем в остовное дерево. Ребро 5-6, вес которого равен 28, образует цикл 6-1-7-3-4-9-8-5. Его не берем в остовное дерево. Ребро 7-6, вес которого равен 36, образует цикл 6-1-7. Его не берем в остовное дерево. Минимальное остовное дерево построено. |
Вебинар для учителей
Свидетельство об участии БЕСПЛАТНО!
Полезное для учителя
Реализация образовательных программ осуществляется с применением исключительно электронного обучения и ДОТ
