Алгоритмы на графах и деревьях
Сравнение алгоритмов КомпСвяз-Рек и КомпСвяз-Итер
В худшем случае (при полном графе ) рекурсивный алгоритм, перебирая все возможные ребра, будет вынужден вызвать основную процедуру (N-1) ! раз. Велика вероятность, что при достаточно большом N произойдет переполнение оперативной памяти, которое вызовет аварийную остановку программы. Кроме того, размеры квадратной матрицы смежности дают сильное ограничение на возможное количество вершин графа : не более 250 (см. лекцию 3).
Итеративный же алгоритм переберет все ребра графа, которых может быть не более чем N*(N+1)/2 . В половине этих случаев возможна ситуация объединения двух компонент связности в одну, для чего потребуется еще N операций. Следовательно, общая сложность алгоритма может быть приблизительно оценена значением N 3 /8 . Возможное количество вершин графа ограничено только максимальным размером линейного массива ( 32 000 ).
Нахождение минимального каркаса
Задача. В заданном взвешенном связном графе определить множество ребер, составляющих некоторый его оптимальный каркас (например, минимальный по сумме весов входящих в него ребер).
Рекурсивный алгоритм
Алгоритм Каркас-Рек
Этот алгоритм базируется на прямом обходе графа, который учитывает два условия: во-первых, чтобы суммарный вес текущего каркаса был меньше текущего минимума и, во-вторых, чтобы в каркасе было ровно N-1 ребро 6 См. предыдущую лекцию. ( N — количество вершин графа ).
Реализация
Для того чтобы помимо суммарного веса каркаса алгоритм также запоминал включенные в каркас ребра, необходимо добавить дополнительный квадратный массив, в котором будут храниться пометки включения ребер в каркас.
Итеративный алгоритм
Алгоритм Краскала
- Упорядочить все ребра графа по возрастанию их весов.
- Применить алгоритм КомпСвяз-Итер (см. пункт «Подсчет количества компонент связности «).
Замечание: Выполнение алгоритма Краскала можно завершить сразу же, как только в каркас будет добавлено ( N-1 )-е ребро (поскольку в дереве с N вершинами должно быть ровно N-1 ребро).
Реализация
Реализация основной части алгоритма (шаг 2) совпадает с реализацией алгоритма КомпСвяз-Итер, за исключением того, что в случаях 1, 2 и 4 необходимо ввести подсчет добавленных в каркас ребер, а внешний цикл завершить не в момент достижения конца файла, а в момент, когда счетчик добавленных ребер станет равным N-1 .
Нахождение кратчайших путей
Задача. В заданном взвешенном связном графе найти расстояние (длину кратчайшего пути ) от выделенной вершины s до вершины t . Веса всех ребер строго положительны.
Рекурсивный алгоритм
Алгоритм Расст-Рек
Совершить обход графа в глубину , при каждом «шаге вперед» прибавляя длину ребра к длине текущего пути, при каждом возврате — отнимая длину этого ребра от длины текущего пути. При движении «вперед» пометки посещенности вершин ставятся, при «откате» — снимаются. По достижении выделенной вершины t производится сравнение длины текущего пути с ранее найденным минимумом.
Реализация
Пусть граф задан матрицей смежности sm , а массив mark хранит информацию о посещениях вершин. Напомним, что уменьшение длины пути «на возврате» совершается рекурсией автоматически, поскольку в ее заголовке использован параметр-значение , а вот аналогичное обнуление соответствующих позиций массива mark приходится делать вручную, поскольку задавать массив параметром-значением чересчур накладно:
Итеративный алгоритм
Алгоритм , предложенный Дейкстрой 7 Dijkstra E.W. A Note on Two Problems in Connection with Graphs, 1959. , настолько мощнее рекурсивного алгоритма Расст-Рек, что, при тех же начальных условиях и не прикладывая дополнительных усилий, он может найти расстояние от выделенной вершины s не только до одной вершины t , но и до всех остальных вершин графа .
Итак, пусть граф задан матрицей смежности .
Линейный массив dist будет хранить длины текущих путей от вершины s до всех остальных вершин. В начале этот массив будет инициирован числами MaxLongInt , символизирующими «бесконечность». По окончании работы алгоритма в этом массиве останутся только минимальные значения длин путей, которые и являются расстояниями.
Еще один линейный массив done потребуется нам для того, чтобы хранить информацию о том, найден ли уже минимальный путь (он же расстояние) до соответствующей вершины и можно ли исключить эту вершину из дальнейшего рассмотрения.
Переменная last будет хранить номер последней помеченной вершины.
Отметим особо, что на каждом шаге Алгоритм Дейкстры находит длину кратчайшего пути до очередной вершины графа. Именно поэтому достаточно сделать ровно N-1 итераций.
Алгоритм Дейкстры
Расстояние от s до s , конечно же, равно 0 . Кроме того, это расстояние уже никогда не сможет стать меньше — ведь веса всех ребер графа у нас положительны. Таким образом:
Повторить N-1 раз следующие действия:
для всех непомеченных вершин х , связанных ребром с вершиной last , необходимо пересчитать расстояние:
Реализация
Мы надеемся, что функцию поиска меньшего из двух целых чисел min , использованную в тексте программы, читатели смогут написать самостоятельно.
Сравнение алгоритмов Расст-Рек и Дейкстры
Сложность рекурсивного алгоритма пропорциональна N !, а алгоритм Дейкстры имеет сложность
Алгоритм Краскала
Алгоритм Краскала — это алгоритм минимального остовного дерева, что принимает граф в качестве входных данных и находит подмножество ребер этого графа, который формирует дерево, включающее в себя каждую вершину, а также имеет минимальную сумму весов среди всех деревьев, которые могут быть сформированы из графа.
Как работает алгоритм Краскала
Он подпадает под класс алгоритмов, называемых «жадными» алгоритмами , которые находят локальный оптимум в надежде найти глобальный оптимум.
Мы начинаем с ребер с наименьшим весом и продолжаем добавлять ребра, пока не достигнем нашей цели.
Шаги для реализации алгоритма Краскала следующие:
- Сортировать все ребра от малого веса до высокого.
- Возьмите ребро с наименьшим весом и добавьте его в остовное дерево. Если добавление ребра создало цикл, то отклоните это ребро.
- Продолжайте добавлять ребра, пока не достигнете всех вершин.
Пример алгоритма Краскала
Алгоритм Краскала. Псевдокод.
Любой минимальный алгоритм остовного дерева вращается вокруг проверки, создает ли ребро цикл или нет.
Наиболее распространенный способ выяснить это — алгоритм Union FInd . Алгоритм Union-Find разделяет вершины на кластеры и позволяет нам проверить, принадлежат ли две вершины одному кластеру или нет, и, следовательно, решить создает ли добавление ребра цикл.
Реализация алгоритма Краскала в C ++
Ниже приведен код для реализации в C ++. Мы используем стандартные библиотеки шаблонов, чтобы сделать нашу работу проще и чище.
Когда мы запускаем программу, мы получаем вывод как:
Алгоритм Краскала vs Прима
Алгоритм Прима является еще одним популярным алгоритмом минимального остовного дерева, который использует другую логику для нахождения MST графа. Вместо того, чтобы начинать с ребра, алгоритм Прима начинается с вершины и продолжает добавлять ребра с наименьшим весом, которых нет в дереве, пока все вершины не будут покрыты.
Рекомендуем хостинг TIMEWEB
Рекомендуемые статьи по этой тематике
Подписчики
Платёжная система
- mafulechka
- 4847
- 1
- 3
- 0
- Vladimir Sergeevich
- #
- 25 июля 2019 г. 12:20
- (ред.)
Я так понимаю, это перевод статьи?
Вот такие фразы выглядят стремно: «Любой минимальный алгоритм остовного дерева»
«популярным алгоритмом минимального остовного дерева»
Возможно, должно быть «алгоритмом построения . «
Первое предложение тоже несогласованное.
Странной кажется идея запихивания графа в класс. Да и все равно можно выстрелить в ногу, вызвав print до вызова kruskal.
Не очевидна связь приведенного кода с описанным алгоритмом. — Что это за массив parent и почему (кстати) он не уничтожается в деструкторе?
Псевдокод не понятный. Что делает функция UNION(u, v) ?
Обе строки 7 и 8 вложены внутрь блока if?
У нормальной реализации алгоритма сложность N*log(N). А у вас для каждого узла графа вызывается функция find_set, которая имеет трудоемкость O(N). И того — O(N^2). Функция find_set при этом вообще особо кривая. Не понятно что она должна вернуть в каком случае.
Ну и еще, вот эта структура выглядит очень плохо:
vector