Графы. Поиск остова минимального веса. Алгоритм Краскала

Графы широко используются для моделирования сетевых структур. Задача поиска остовного дерева минимального веса позволяет оптимизировать затраты на построение таких сетей. Алгоритм Краскала - эффективное решение для нахождения минимального остовного дерева. Давайте разберемся, как он работает.

Постановка задачи

Рассмотрим формальную и неформальную постановки задачи поиска минимального остовного дерева.

Формальная постановка

Пусть дан неориентированный взвешенный граф G = (V, E) с множеством вершин V и множеством ребер E c весами w(e) для каждого ребра e.

Требуется найти такое подмножество ребер E' ⊆ E, что граф G' = (V, E'):

1. Является деревом (связен и ацикличен)
2. Соединяет все вершины графа G
3. Имеет минимальную сумму весов w(E') среди всех остовных деревьев графа G

Такое дерево называется минимальным остовным деревом (МОД) графа G.

Неформальная постановка

Другими словами, нам нужно найти такой набор ребер, который соединяет все вершины графа без образования циклов и имеет наименьшую суммарную стоимость (сумму весов ребер).

Ниже приведен пример исходного графа, для которого нужно найти МОД:

Практически эта задача часто возникает при проектировании транспортных или компьютерных сетей, когда нужно соединить все точки с минимальными затратами.

Обзор алгоритма Краскала

Алгоритм Краскала - это классический жадный алгоритм для нахождения МОД в графе.

Рассмотрим как он работает. На начальном этапе каждая вершина графа помещается в свое отдельное дерево. Затем на каждой итерации алгоритм объединяет два дерева с помощью добавления ребра между ними. Ребра выбираются в порядке неубывания их весов, причем так чтобы не образовывать циклы. Процесс продолжается до тех пор, пока не останется одно дерево, охватывающее все вершины графа.

Достоинства и недостатки

К достоинствам алгоритма Краскала можно отнести:

• Простота реализации
• Хорошая асимптотическая сложность O(E log V)
• Гарантированно находит оптимальное решение

К недостаткам относятся:

• Необходимость предварительной сортировки всех ребер по весу
• Замедляется на разреженных графах с большим количеством ребер

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

Разбор алгоритма на примере

Давайте пошагово разберем работу алгоритма Краскала на примере графа, приведенного выше.

Шаг 1. Сортировка ребер

В соответствии с алгоритмом, сначала выполняется сортировка всех ребер графа по неубыванию весов:

Дальнейшие шаги алгоритма будут состоять в последовательном рассмотрении ребер из этого списка.

Шаг 2. Добавление первого ребра

Рассматривается ребро A-B с наименьшим весом 7. Так как оно соединяет разные деревья, содержащие вершины A и B, то добавляется в остов.

Полученный на данном этапе остов выглядит так:

Далее рассматривается следующее ребро B-C с весом 11.

Шаг 3. Добавление второго ребра

Ребро B-C также соединяет разные деревья, содержащие B и C, поэтому оно добавляется

На данном шаге мы получили уже связный остов, охватывающий все вершины исходного графа. Однако он пока не является минимальным, поэтому алгоритм продолжает работу.

Шаг 4. Проверка оставшихся ребер

Далее проверяются оставшиеся ребра в порядке сортировки. Однако все они при добавлении создадут цикл, что недопустимо для остовного дерева.

Поэтому на последнем шаге алгоритм останавливается, и в качестве ответа возвращается построенный остов:

Это и есть минимальное остовное дерево исходного графа, найденное с помощью алгоритма Краскала. Его суммарный вес равен 7 + 11 = 18.

Шаг 4. Проверка оставшихся ребер

Далее проверяются оставшиеся ребра в порядке сортировки. Однако все они при добавлении создадут цикл, что недопустимо для остовного дерева.

Сравнение с эталонным МОД

Для проверки корректности работы алгоритма сравним полученный результат с эталонным МОД, найденным другим методом:

Мы видим, что остовные деревья совпадают. Значит, алгоритм Краскала правильно нашел минимальный остов для данного графа.

Анализ результатов

Подводя итоги примера, можно сделать следующие выводы об алгоритме Краскала:

• Шаг за шагом строится остовное дерево путем объединения фрагментов
• Гарантированно дает оптимальный результат за O(E log V) операций
• Прост в реализации

Другой пример графа

Для дополнительной иллюстрации работы алгоритма применим его к другому графу:

После сортировки ребер получаем следующую последовательность:

1. C-D
2. A-B
3. B-D
4. A-C

Применяя алгоритм Краскала к этому списку ребер, получим МОД, показанное

Итого, мы убедились, что алгоритм Краскала позволяет эффективно строить минимальный остов для произвольного графа. Рассмотрев его работу на конкретных примерах, мы можем сделать следующие ключевые выводы:

• Алгоритм последовательно объединяет фрагменты остова с помощью добавления ребер
• Ключевым моментом является проверка, создает ли новое ребро цикл
• Краскал гарантированно дает оптимальный МОД за O(E log V) операций

Реализация алгоритма Краскала

Рассмотрим основные моменты реализации алгоритма Краскала на языке программирования С++.

Структуры данных

В алгоритме используются следующие структуры данных:

• Массив вершин графа
• Структура ребра с полями начальная вершина, конечная вершина и вес
• Массив ребер
• Дисъюнктивное множество для хранения деревьев

Основные этапы

Пошагово алгоритм можно реализовать так:

1. Заполнение массива вершин
2. Заполнение массива ребер и их сортировка по весу
3. Создание дисъюнктивных множеств для каждой вершины
4. Перебор отсортированных ребер
5. Проверка, соединяет ли ребро разные множества
6. Объединение множеств и добавление ребра к остову

Тестирование

Реализацию алгоритма необходимо протестировать на разных графах и сравнить результаты с эталонными МОД. Это позволит выявить возможные ошибки.

Оптимизированный алгоритм Краскала

Рассмотрим возможности оптимизации алгоритма Краскала с использованием системы непересекающихся множеств (СНМ).

В СНМ каждому элементу ставится в соответствие некоторый идентификатор его множества. Чтобы проверить, лежат ли два элемента в одном множестве, достаточно сравнить их идентификаторы. А для объединения множеств нужно всего лишь присвоить один идентификатор всем их элементам.

Преимущества СНМ

• Быстрая проверка принадлежности к множеству за O(1)
• Быстрое объединение множеств за O(1)

Это позволяет ускорить работу алгоритма Краскала до O(E log E).

Реализация СНМ

Один из вариантов реализации СНМ - это использование деревьев с указателями на родительские элементы. Корень дерева задает идентификатор множества.