анти. Guide to Competitive
 Скачать 2.39 Mb.
|
|
7.3. Кратчайшие пути Нахождение кратчайшего пути между двумя вершинами графа – важная задача, имеющая много практических применений. Очевидный пример – нахождение кратчайшего маршрута между двумя городами, если известна карта дорог и длины всех участков. В невзвешенном графе длина пути равна количеству ребер в нем, и для поиска кратчайшего пути достаточно применить поиск в ширину. Но 2 1 3 5 4 Рис. 7.17. Конфликт при проверке на двудольность 112 Глава 7. Алгоритмы на графах в этом разделе нас будут интересовать взвешенные графы, для которых нужны более сложные алгоритмы. 7.3.1. Алгоритм Беллмана–Форда Алгоритм Беллмана–Форда находит кратчайшие пути из начальной вер- шины во все вершины графа. Алгоритм применим к любым графам, не содержащим цикла с отрицательной длиной. Если граф содержит такой цикл, то алгоритм обнаружит это. Алгоритм запоминает расстояния от начальной вершины до всех вер- шин графа. В начальный момент расстояние до начальной вершины равно 0, а до всех остальных бесконечно. Затем алгоритм уменьшает расстояния, отыскивая ребра, которые укорачивают пути, и останавливается, когда ни одно расстояние нельзя уменьшить. На рис. 7.18 показано, как алгоритм Беллмана–Форда обрабатывает граф. Сначала алгоритм уменьшает расстояния, используя ребра 1 → 2, 1 → 3 и 1 → 4, затем – используя ребра 2 → 5 и 3 → 4, и, наконец, ис- пользуя ребро 4 → 5. После этого не осталось ребер, с помощью которых можно уменьшить расстояния, и, значит, найденные расстояния окон- чательны. 1 2 3 4 5 0 ∞ ∞ ∞ ∞ 2 3 − 2 3 5 2 7 Шаг 1 1 2 3 4 5 0 2 3 7 ∞ 2 3 − 2 3 5 2 7 Шаг 2 1 2 3 4 5 0 2 3 1 7 2 3 − 2 3 5 2 7 Шаг 3 1 2 3 4 5 0 2 3 1 3 2 3 − 2 3 5 2 7 Шаг 4 Рис. 7.18. Алгоритм Беллмана–Форда Реализация. Приведенная ниже реализация алгоритма Беллмана–Фор- да определяет кратчайшие расстояния от вершины x до всех вершин гра- фа. Предполагается, что граф представлен списком ребер, содержащим кортежи вида (a,b,w); каждый такой кортеж означает, что существует реб- ро веса w, соединяющее вершины a и b. 7.3. Кратчайшие пути 113 Алгоритм состоит из n − 1 раундов. На каждом раунде алгоритм переби- рает все ребра графа и пытается уменьшить расстояния. Строится массив distance , в котором хранятся расстояния от вершины x до каждой верши- ны графа. Константа INF обозначает бесконечное расстояние. for (int i = 1; i <= n; i++) { distance[i] = INF; } distance[x] = 0; for (int i = 1; i <= n-1; i++) { for (auto e : edges) { int a, b, w; tie(a, b, w) = e; distance[b] = min(distance[b], distance[a]+w); } } Временная сложность этого алгоритма равна O(nm), поскольку на каж- дом из n − 1 раундов перебираются все m ребер. Если в графе нет отрица- тельных циклов, то после n − 1 раундов расстояния уже не могут изменить- ся, потому что любой кратчайший путь содержит не более n − 1 ребер. На практике алгоритм можно оптимизировать несколькими способами. Во-первых, окончательные расстояния обычно становятся известны еще до выполнения всех n − 1 раундов, так что можно просто остановить алго- ритм, если в очередном раунде ни одно расстояние не удалось уменьшить. Существует также усовершенствованный алгоритм SPFA (Shortest Path Faster Algorithm – ускоренный алгоритм поиска кратчайшего пути [10]), который поддерживает очередь вершин, потенциально способных умень- шить расстояния. Обрабатывать нужно лишь вершины из этой очереди, что часто повышает эффективность поиска. Отрицательные циклы. Алгоритм Беллмана– Форда можно использовать также для проверки наличия циклов с отрицательной длиной. В этом случае длину любого пути, содержащего такой цикл, можно уменьшать бесконечно много раз, поэтому понятие кратчайшего пути теряет смысл. Например, граф на рис. 7.19 содержит отрицатель- ный цикл 2 → 3 → 4 → 2 длины −4. Для обнаружения отрицательного цикла с помощью алгоритма Белл- мана–Форда нужно выполнить n раундов алгоритма. Если в последнем раунде хотя бы одно расстояние уменьшилось, то граф содержит отрица- тельный цикл. Отметим, что этот алгоритм обнаруживает отрицательный цикл вне зависимости от выбора начальной вершины. 1 2 3 4 3 1 5 − 7 2 Рис. 7.19. Граф с отрицательным циклом 114 Глава 7. Алгоритмы на графах 7.3.2. Алгоритм Дейкстры Алгоритм Дейкстры, как и алгоритм Беллмана–Форда, находит кратчай- шие пути из начальной вершины во все вершины графа. Но он более эф- фективен и может применяться для обработки графов большого размера. Однако требуется, чтобы в графе не было ребер с отрицательным весом. Как и алгоритм Беллмана–Форда, алгоритм Дейкстры хранит расстоя- ния до вершин и уменьшает их в процессе поиска. На каждом шаге алго- ритм Дейкстры выбирает из еще не обработанных вершин ту, до которой расстояние минимально. Затем перебираются все ребра, начинающие- ся в этой вершине, и с их помощью уменьшаются расстояния. Алгоритм Дейкст ры эффективен, потому что каждое ребро обрабатывается только один раз – так как в графе нет ребер с отрицательным весом. На рис. 7.20 показано, как алгоритм Дейкстры обрабатывает граф. Как и в алгоритме Беллмана–Форда, начальные расстояния до всех вершин, кро- ме стартовой, равны бесконечности. Алгоритм обрабатывает вершины в порядке 1, 5, 4, 2, 3 и каждый раз уменьшает расстояния с помощью ребер, начинающихся в текущей вершине. Отметим, что после обработки любой вершины расстояние до нее больше не изменяется. 3 4 2 1 5 ∞ ∞ ∞ 0 ∞ 6 2 5 9 2 1 Шаг 1 3 4 2 1 5 ∞ 9 5 0 1 6 2 5 9 2 1 Шаг 2 3 4 2 1 5 ∞ 3 5 0 1 6 2 5 9 2 1 Шаг 3 3 4 2 1 5 9 3 5 0 1 6 2 5 9 2 1 Шаг 4 3 4 2 1 5 7 3 5 0 1 6 2 5 9 2 1 Шаг 5 3 4 2 1 5 7 3 5 0 1 6 2 5 9 2 1 Шаг 6 Рис. 7.20. Алгоритм Дейкстры 7.3. Кратчайшие пути 115 Реализация. Для эффективной реализации алгоритма Дейкстры необ- ходимо эффективно находить еще не обработанную вершину, отстоящую на минимальное расстояние. Для этого подойдет очередь с приоритетом, в которой оставшиеся вершины хранятся, упорядоченные по возрастанию расстояния. Эта структура данных позволяет найти следующую вершину за логарифмическое время. В типичной реализации алгоритма Дейкстры из учебника использует- ся очередь с приоритетом, предоставляющая операцию изменения нахо- дящегося в очереди значения. Это дает возможность хранить в очереди единственный экземпляр каждой вершины и обновлять расстояние до него по мере необходимости. Но очередь с приоритетом из стандартной библиотеки не предоставляет такой операции, поэтому в олимпиадном программировании обычно используется несколько иная реализация. Идея в том, чтобы добавлять в очередь новый экземпляр вершины всякий раз, как изменяется расстояние до нее. Наша реализация алгоритма Дейкстры вычисляет минимальные расстоя- ния от вершины x до всех остальных вершин графа. Граф представлен в виде списков смежности, так что adj [a ] содержит пару (b, w), если сущест- вует ребро веса w, соединяющее вершины a и b. Очередь с приоритетом priority_queue int,int>> q; содержит пары вида (−d, x), означающие, что текущее расстояние до вер- шины x равно d. Массив distance содержит расстояния до всех вершин, а массив processed позволяет узнать, была ли вершина обработана. Отметим, что в очереди с приоритетом хранятся расстояния до вершин со знаком минус. Дело в том, что по умолчанию реализация очереди в стан- дартной библиотеке C++ находит максимальный элемент, а нам нужен ми- нимальный. Изменив знак расстояния, мы сможем воспользоваться име- ющейся реализацией очереди без каких-либо изменений 2 . Отметим также, что в очереди может находиться несколько экземпляров вершины, но об- работан будет только тот экземпляр, в котором расстояние минимально. Код приведен ниже: for (int i = 1; i <= n; i++) { distance[i] = INF; } distance[x] = 0; q.push({0,x}); while (!q.empty()) { int a = q.top().second; q.pop(); if (processed[a]) continue; 2 Конечно, можно было бы объявить очередь, как описано в разделе 5.2.3, и пользоваться положи- тельными расстояниями, но реализация стала бы длиннее. 116 Глава 7. Алгоритмы на графах processed[a] = true; for (auto u : adj[a]) { int b = u.first, w = u.second; if (distance[a]+w < distance[b]) { distance[b] = distance[a]+w; q.push({-distance[b],b}); } } } Временная сложность этой реализации равна O(n + m log m), потому что алгоритм перебирает все вершины графа и для каждого ребра добавляет в очередь с приоритетом не более одного расстояния. Отрицательные ребра. Эффективность алго- ритма Дейкстры основана на том, что в графе нет отрицательных ребер. Если же такие ребра при- сутствуют, то алгоритм может давать неправиль- ные результаты. Рассмотрим граф на рис. 7.21. Из вершины 1 в вершину 4 ведет кратчайший путь 1 → 3 → 4, его длина равна 1. Однако алгоритм Дейкстры неправильно находит путь 1 → 2 → 4, поскольку жадно следует по ребрам с минималь- ным весом. 7.3.3. Алгоритм Флойда–Уоршелла Алгоритм Флойда–Уоршелла предлагает другой подход к задаче поиска кратчайших путей. В отличие от других алгоритмов, он находит кратчай- шие пути между всеми парами вершин за один проход. Алгоритм манипулирует матрицей, содержащей расстояния между па- рами вершин. В начальный момент матрица инициализируется на осно- ве матрицы смежности. Затем алгоритм выполняет несколько раундов, на каждом из которых выбирает новую вершину, которая в дальнейшем может быть промежуточной вершиной в путях, и уменьшает расстояния, используя эту вершину. Продемонстрируем работу алгоритма Флойда–Уоршелла на примере графа на рис. 7.22. В этом случае начальная матрица выглядит так: 0 5 9 1 5 0 2 2 0 7 9 7 0 2 1 2 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 1 2 3 4 2 3 6 − 5 Рис. 7.21. Пример графа, на котором алгоритм Дейкстры дает невер- ный результат 7.3. Кратчайшие пути 117 3 4 2 1 5 7 2 5 9 2 1 Рис. 7.22. Входные данные для алгоритма Флойда–Уоршелла В первом раунде новой промежуточной вершиной становится верши- на 1. Между вершинами 2 и 4 обнаруживается новый путь длины 14, по- скольку их соединяет вершина 1. Обнаруживается также новый путь дли- ны 6 между вершинами 2 и 5. 0 5 9 1 5 0 2 2 0 7 9 7 0 2 1 2 0 ∞ ∞ ∞ ∞ 14 6 14 6 Во втором раунде новой промежуточной вершиной становится верши- на 2. В результате создаются новые пути между вершинами 1 и 3 и верши- нами 3 и 5. 0 5 9 1 5 0 2 14 6 2 0 7 9 14 7 0 2 1 6 2 0 7 7 8 8 Алгоритм продолжает работу до тех пор, пока все вершины не окажутся промежуточными. И в этот момент матрица будет содержать минималь- ные расстояния между всеми парами вершин: 0 5 7 3 1 5 0 2 8 6 7 2 0 7 8 3 8 7 0 2 1 6 8 2 0 Например, мы видим, что кратчайшее расстояние между вершинами 2 и 4 равно 8. Ему соответствует путь, показанный на рис. 7.23. 118 Глава 7. Алгоритмы на графах 3 4 2 1 5 7 2 5 9 2 1 Рис. 7.23. Кратчайший путь между вершинами 2 и 4 Реализация. Реализовать алгоритм Флойда–Уоршелла очень просто. Приведенная ниже реализация строит матрицу расстояний, в которой эле- мент dist [a ][b] равен кратчайшему расстоянию между вершинами a и b. Вначале алгоритм инициализирует dist на основе матрицы смежности графа adj : for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { if (i == j) dist[i][j] = 0; else if (adj[i][j]) dist[i][j] = adj[i][j]; else dist[i][j] = INF; } } После этого кратчайшие расстояния можно найти следующим образом: for (int k = 1; k <= n; k++) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]); } } } Временная сложность алгоритма равна O(n 3 ), так как он содержит три вложенных цикла, в которых перебираются вершины графа. Поскольку реализация алгоритма Флойда–Уоршелла так проста, его можно порекомендовать даже тогда, когда требуется найти лишь один кратчайший путь в графе. Однако его можно использовать только для не- больших графов, когда кубическая временная сложность приемлема. 7.4. Ориентированные ациклические графы Важный класс графов составляют ориентированные ациклические графы (directed acyclic graph – DAG). Такие графы не содержат циклов, и если это предположение допустимо, то многие задачи решаются проще. В частно- сти, можно выполнить топологическую сортировку графа, а затем приме- нить динамическое программирование. 7.4. Ориентированные ациклические графы 119 7.4.1. Топологическая сортировка Топологической сортировкой называется упорядочение вершин графа – такое, что если существует путь из вершины a в вершину b, то вершина a будет записана раньше b. На рис. 7.24 показана одна из возможных топо- логических сортировок – [4, 1, 5, 2, 3, 6]. 1 2 3 4 5 6 1 2 3 4 5 6 Рис. 7.24. Граф и его топологическая сортировка Ориентированный граф допускает топологическую сортировку тогда и только тогда, когда он является ациклическим. Если граф содержит цикл, то построить топологическую сортировку невозможно, потому что ни одна вершина цикла не может предшествовать никакой другой в смысле топологического порядка. Оказывается, что поиск в глубину позволяет как проверить наличие циклов в ориентированном графе, так и построить то- пологическую сортировку, если циклов нет. Идея заключается в том, чтобы перебирать вершины графа и начинать поиск в глубину в текущей вершине, если она еще не была обработана. В процессе поисков вершина может находиться в одном из трех состояний: • состояние 0: вершина еще не обработана (белая); • состояние 1: вершина обрабатывается (светло-серая); • состояние 2: вершина обработана (темно-серая). Вначале все вершины находятся в состоянии 0. Когда поиск в первый раз доходит до некоторой вершины, та переходит в состояние 1. После того как все исходящие из вершины ребра будут обработаны, вершина перейдет в состояние 2. Если граф содержит цикл, мы обнаружим это в процессе поиска, потому что рано или поздно наткнемся на вершину в состоянии 1. В таком случае построить топологическую сортировку невозможно. Если же граф не со- держит циклов, то мы сумеем построить топологическую сортировку, до- бавляя в список вершины в момент их перехода в состояние 2. Теперь все готово к построению топологической сортировки графа из примера. Первый поиск (рис. 7.25) переходит от вершины 1 к вершине 6 и добавляет в список вершины 6, 3, 2 и 1. Затем второй поиск (рис. 7.26) переходит от вершины 4 к вершине 5 и добавляет в список вершины 5 и 4. 120 Глава 7. Алгоритмы на графах Окончательный инвертированный список [4, 5, 1, 2, 3, 6] определяет то- пологическую сортировку (рис. 7.27). Отметим, что топологическая сорти- ровка не единственна, для одного и того же графа может быть несколько топологических сортировок. 1 2 3 4 5 6 1 2 3 4 5 6 Рис. 7.25. При первом поиске в список добавляются вершины 6, 3, 2 и 1 Рис. 7.26. При втором поиске в список добавляются вершины 5 и 4 1 2 3 4 5 6 Рис. 7.27. Окончательная топологическая сортировка На рис. 7.28 показан граф, не имеющий топологической сортировки. В процессе поиска мы встречаем вершину 2 в состоянии 1, а это индикатор того, что граф содержит цикл. И действительно, налицо цикл 2 → 3 → 5 → 2. 1 2 3 4 5 6 Рис. 7.28. У этого графа нет топологической сортировки, поскольку он содержит цикл 7.4.2. Динамическое программирование Динамическое программирование позволяет эффективно отвечать на многие вопросы о путях в ориентированных ациклических графах, напри- мер: • какой самый короткий или самый длинный путь из вершины a в вершину b? • сколько существует различных путей? • чему равно минимальное (максимальное) количество ребер в пути? • какие вершины встречаются в каждом возможном пути? Отметим, что для графов общего вида многие из сформулированных выше задач решить трудно или они некорректно поставлены. Для примера решим задачу о вычислении количества путей из верши- ны a в вершину b. Обозначим paths (x)количества путей из вершины a 7.4. Ориентированные ациклические графы 121 в вершину x. Базой рекурсии является равенство paths (a)= 1. А paths (x) для других значений аргумента вычисляется по рекуррентной формуле paths (x)= paths (s 1 )+ paths (s 2 )+ … + paths (s k ), где s 1 , s 2 , …, s k – вершины, для которых существует ребро, ведущее в x. По- скольку граф ациклический, значения paths можно вычислять в порядке топологической сортировки. На рис. 7.29 показаны значения paths для нашего примера, в котором мы хотим вычислить количе- ство путей из вершины 1 в вершину 6. Имеем paths (6) = paths (2) + paths (3), поскольку в вершине 6 заканчиваются ребра 2 → 6 и 3 → 6. Так как paths (2) = 2 и paths (3) = 2, мы за- ключаем, что paths(6) = 4. Вот эти пути: • 1 → 2 → 3 → 6; • 1 → 2 → 6; • 1 → 4 → 5 → 2 → 3 → 6; • 1 → 4 → 5 → 2 → 6. Обработка кратчайших путей. Динамическим программированием можно также воспользоваться для ответов на вопросы, касающиеся крат- чайших путей в графах общего вида (необязательно ациклических). Точнее, если мы знаем минимальные расстояния от начальной вершины до дру- гих вершин (например, в результате применения алгоритма Дейкстры), то легко можем создать ориентированный ациклический граф кратчайших путей, который для каждой вершины показывает возможные способы ее достижения из начальной вершины по кратчайшему пути. Так, на рис. 7.30 показаны граф и соответствующий ему граф кратчайших путей. 1 2 3 4 5 3 5 4 8 2 1 2 1 2 3 4 5 3 5 4 2 1 2 Рис. 7.30. Граф и его граф кратчайших путей 1 2 3 4 5 6 1 1 4 1 2 2 Рис. 7.29. Вычисление количества путей из вершины 1 в вершину 6 122 Глава 7. Алгоритмы на графах Еще раз о размене монет. На самом деле любую задачу динамиче- ского программирования можно представить в виде ориентированного ациклического графа, в котором каждая вершина соответствует состоянию динамического программирования, а ребра показывают, как состояния зависят друг от друга. Рассмотрим, к примеру, задачу о размене суммы n монетами номиналов { c 1 , c 2 , …, c k } (раздел 6.1.1). В этом случае мы можем построить граф, в кото- ром каждая вершина соответствует денежной сумме, а ребра показывают, как можно выбирать монеты. Так, на рис. 7.31 показан граф для монет с номиналами {1, 3, 4} и n = 6. При таком представлении кратчайший путь из вершины 0 в вершину n соответствует решению с наименьшим числом монет, а общее число путей из вершины 0 в вершину n равно общему числу решений. 0 1 2 3 4 5 6 Рис. 7.31. Задача о размене монет как ориентированный ациклический граф 7.5. Графы преемников Еще один специальный класс ориентированных графов – графы преем- ников (successor graph), в которых полустепень исхода каждой вершины равна 1, т. е. у каждой вершины всего один преемник. Граф преемников со- стоит из одной или нескольких компонент связности. Каждая компонента содержит один цикл, в который могут вести несколько путей. Графы преемников иногда называют функциональными графами, потому что любому графу преемников соответствует функция succ (x), определяю- щая ребра графа. В качестве параметра x выступает вершина графа, а зна- чением функции является преемник этой вершины. Например, следую- щая функция x 1 2 3 4 5 6 7 8 9 succ(x) 3 5 7 6 2 2 1 6 3 определяет граф, изображенный на рис. 7.32. 1 2 3 4 5 6 7 8 9 Рис. 7.32. Граф преемников 7.5. Графы преемников 123 7.5.1. Нахождение преемников Поскольку у каждой вершины графа преемников имеется ровно один преемник, мы можем определить функцию succ (x, k), которая возвращает вершину, в которую мы попадем, если выйдем из вершины x и сделаем k шагов вперед. В графе на рис. 7.32 succ (4, 6) = 2, так как, выйдя из верши- ны 4, мы через 6 шагов попадем в вершину 2 (рис. 7.33). 4 6 2 5 2 5 2 Рис. 7.33. Проход по графу преемников Вычислить succ (x, k) можно «в лоб» – начать с вершины x и сделать k ша- гов вперед; это займет время O(k). Однако после некоторой предваритель- ной обработки любое значение succ (x, k)можно будет вычислить за время O(log k). Обозначим u максимальное количество шагов, которое нас в принципе может интересовать. Идея заключается в том, чтобы заранее вычислить все значения succ (x, k), где k – степень двойки, не превосходящая u. Это можно сделать эффективно, потому что имеет место следующее рекур- рентное соотношение: succ (x, k) k = 1 succ (x, k) = � succ (succ(x, k/2), k/2) k > 1 , поскольку любой путь длины k, начинающийся в вершине x, можно раз- бить на два пути длины k/2. Вычисление всех значений succ (x, k), где k – степень двойки, не превосходящая u, занимает время O(n log u), так как для каждой вершины вычисляется O(log u)значений. В нашем примере первые значения таковы: x 1 2 3 4 5 6 7 8 9 succ(x , 1) 3 5 7 6 2 2 1 6 3 succ(x , 2) 7 2 1 2 5 5 3 2 7 succ(x , 4) 3 2 7 2 5 5 1 2 3 succ(x , 8) 7 2 1 2 5 5 3 2 7 После этого предварительного вычисления любое значение succ (x, k) можно вычислить, представив k в виде суммы степеней двойки. В таком представлении будет O(log k)слагаемых, поэтому вычисление succ (x, k)за- нимает время O(log k). Например, для вычисления succ (x, 11) мы восполь- зуемся формулой succ (x, 11) = succ ( succ ( succ (x, 8), 2), 1). 124 Глава 7. Алгоритмы на графах В случае нашего графа succ (4, 11) = succ ( succ ( succ (4, 8), 2), 1) = 5. 7.5.2. Обнаружение циклов Рассмотрим граф преемников, который содержит только путь, закан- чивающийся циклом. Мы можем задать следующие вопросы: если вый- ти из начальной вершины, то какова будет первая встреченная вершина, принадлежащая циклу, и сколько всего вершин содержит цикл? Так, на рис. 7.34 мы начинаем проход с вершины 1, первой встреченной верши- ной, принадлежащей циклу, будет 4, а всего в цикле три вершины (4, 5, 6). 5 4 6 3 2 1 Рис. 7.34. Цикл в графе преемников Существует простой способ обнаружить цикл: идти по графу и запоми- нать все посещенные вершины. Как только некоторая вершина встретится во второй раз, мы можем сказать, что она и является первой вершиной цикла. Этот метод требует времени O(n)и потребляет память объемом O(n). Но имеются и более эффективные алгоритмы обнаружения циклов. Их временная сложность по-прежнему равна O(n), но зато они потребляют всего O(1) памяти, что может быть существенно при больших n. Одним из них является алгоритм Флойда, который проходит по графу и использует два указателя a и b. Вначале оба указывают на начальную вер- шину x. На каждой итерации a сдвигается вперед на один шаг, а b – на два шага. Процесс продолжается, пока оба указателя не встретятся: a = succ(x); b = succ(succ(x)); while (a != b) { a = succ(a); b = succ(succ(b)); } В этот момент указатель a прошел k шагов, а указатель b – 2k шагов, поэтому длина цикла делит k. Следовательно, первую вершину, принад- лежащую циклу, можно найти, переставив указатель a на x и продвигая указатели вперед по одному шагу, пока они снова не встретятся. a = x; while (a != b) { a = succ(a); 7.6. Минимальные остовные деревья 125 b = succ(b); } first = a; Теперь длину цикла можно найти следующим образом: b = succ(a); length = 1; while (a != b) { b = succ(b); length++; } 7.6. Минимальные остовные деревья Остовное дерево содержит все вершины графа и некоторое подмножество его ребер, такое, что любые две вершины соединены путем, проходящим по этим ребрам. Как и любое дерево, остовное дерево является связным ациклическим графом. Весом остовного дерева называется суммарный вес его ребер. На рис. 7.35 показаны граф и одно из его остовных деревьев. Вес этого дерева равен 3 + 5 + 9 + 3 + 2 = 22. 1 2 3 4 5 6 3 5 9 5 2 7 6 3 1 2 3 4 5 6 3 5 9 2 3 Рис. 7.35. Граф и его остовное дерево Минимальным остовным деревом называется остовное дерево мини- мального веса. На рис. 7.36 показано минимальное остовное дерево вы- шеупомянутого графа с весом 20. Аналогично максимальным остовным деревом называется остовное дерево максимального веса. На рис. 7.37 по- казано максимальное остовное дерево того же графа с весом 32. Отметим, что у графа может быть несколько минимальных и максимальных остов- ных деревьев. Для построения минимального и максимального остовных деревьев есть несколько жадных алгоритмов. В этом разделе обсуждаются два ал- 126 Глава 7. Алгоритмы на графах горитма, которые обрабатывают ребра графа, упорядоченные по весу. Мы будем искать минимальное остовное дерево, но для поиска максимально- го остовного дерева применимы те же алгоритмы – только ребра нужно обрабатывать в противоположном порядке. 1 2 3 4 5 6 3 5 2 7 3 1 2 3 4 5 6 5 9 5 7 6 Рис. 7.36. Минимальное остовное дерево с весом 20 Рис. 7.37. Максимальное остовное дерево с весом 32 7.6.1. Алгоритм Краскала Алгоритм Краскала строит минимальное остовное дерево, жадно добав- ляя в граф ребра. Начальное остовное дерево содержит только вершины графа и ни одного ребра. Затем алгоритм перебирает ребра, отсортиро- ванные в порядке возрастания весов, и всякий раз добавляет ребро в граф, если при этом не образуется цикл. Алгоритм манипулирует компонентами связности графа. Вначале каж- дая вершина графа принадлежит отдельной компоненте. При добавлении в граф нового ребра две компоненты объединяются. В конце все верши- ны будут принадлежать одной компоненте, она и является минимальным остовным деревом. Для примера построим минимальное остовное дерево графа на рис. 7.35. Первым делом отсортируем ребра в порядке возрастания весов: Ребро Вес 5–6 2 1–2 3 3–6 3 1–5 5 2–3 5 2–5 6 4–6 7 3–4 9 Затем проходим по списку и добавляем ребро в граф, если оно соединя- ет две разные компоненты. Шаги алгоритма показаны на рис. 7.38. В на- чальный момент каждая вершина принадлежит своей компоненте. Затем в граф добавляются первые ребра из списка (5–6, 1–2, 3–6 и 1–5). Следую- 7.6. Минимальные остовные деревья 127 щее ребро, 2–3, не добавляется, потому что это привело бы к образованию цикла. Так же обстоит дело для ребра 2–5. Ребро 4–6 добавляется, после чего минимальное остовное дерево готово. 1 2 3 4 5 6 Шаг 1 1 2 3 4 5 6 2 Шаг 2 1 2 3 4 5 6 3 2 Шаг 3 1 2 3 4 5 6 3 2 3 Шаг 4 1 2 3 4 5 6 3 5 2 3 Шаг 5 1 2 3 4 5 6 3 5 2 7 3 Шаг 6 Рис. 7.38. Алгоритм Краскала Почему это работает? А действительно – по- чему алгоритм Краскала работает? Почему жад- ная стратегия гарантирует нахождение именно минимального остовного дерева? Посмотрим, что произойдет, если ребро с минимальным ве- сом не включено в остовное дерево – в нашем случае это означает, что не включено ребро 5–6. Мы не знаем точную структуру такого остовного дерева, но какие-то ребра оно должно содержать наверняка. Предположим, что дерево выглядит, как показано на рис. 7.39. Однако остовное дерево на рис. 7.39 не может быть минимальным, потому что никто не меша- ет нам удалить из него какое-то ребро и заменить его ребром с минимальным весом 5–6. Получит- ся остовное дерево с меньшим весом, показанное на рис. 7.40. 1 2 3 4 5 6 Рис. 7.39. Гипотетическое минимальное остовное дерево 1 2 3 4 5 6 2 Рис. 7.40. Включение ребра 5–6 уменьшает вес остовного дерева 128 Глава 7. Алгоритмы на графах Поэтому включать ребро с минимальным весом необходимо, если мы хотим получить минимальное остовное дерево. Применяя аналогичное рассуждение, можно показать, что необходимо включать также ребро со следующим по величине весом и т. д. Поэтому алгоритм Краскала всегда дает минимальное остовное дерево. Реализация. При реализации алгоритма Краскала удобно использовать представление графа в виде списка ребер. На первом этапе мы сортируем этот список за время O(m log m), а на втором этапе строим минимальное остовное дерево: for (...) { if (!same(a,b)) unite(a,b); } Цикл перебирает находящиеся в списке ребра и обрабатывает каждое ребро (a, b), соединяющее вершины a и b. Нам необходимы две функции: same определяет, принадлежат ли вершины a и b одной связной компонен- те, а unite объединяет компоненты, содержащие a и b. Проблема в том, как эффективно реализовать функции same и unite Можно, например, реализовать same в виде обхода графа и проверить, су- ществует ли путь из a в b. Но временная сложность такой функции была бы равна O(n + m), и алгоритм работал бы слишком медленно, т. к. same вызывается для каждого ребра графа. Мы решим задачу с помощью системы непересекающихся множеств – структуры данных, позволяющей реализовать обе функции за время O(log n). Таким образом, временная сложность алгоритма Краскала после сортировки списка ребер будет равна O(m log n). 7.6.2. Система непересекающихся множеств Система непересекающихся множеств (union-find structure) состоит из коллекции множеств. Эти множества попарно не пересекаются, т. е. каж- дый элемент принадлежит только одному множеству. Поддерживаются две операции с временной сложностью O(log n): unite объединяет два множества, а find находит представителя множества, содержащего задан- ный элемент. В системе непересекающихся множеств в каждом множестве выбирается по одному представителю, и существует путь от любого элемента множества к его представителю. Рассмотрим, к примеру, множества {1, 4, 7}, {5} и {2, 3, 6, 8}. На рис. 7.41 показано, как можно их представить. В данном случае представителями являются элементы 4, 5 и 2. Чтобы найти представителя любого элемента, нужно проследовать по пути, кото- рый начинается в этом элементе. Например, элемент 2 является предста- вителем элемента 6, потому что существует путь 6 → 3 → 2. Два элемента 7.6. Минимальные остовные деревья 129 принадлежат одному и тому же множеству тогда и только тогда, когда у них одинаковые представители. Чтобы объединить два множества, представитель одного соединяется с представителем другого. На рис. 7.42 показан один из способов соединить множества {1, 4, 7} и {2, 3, 6, 8}. Начиная с этого момента представителем всего множества является элемент 2, а старый представитель 4 указывает на него. 1 2 3 4 5 6 7 8 1 2 3 4 6 7 8 Рис. 7.41. Система трех непересекающихся множеств Рис. 7.42. Объединение двух множеств в одно Эффективность системы непересекающихся множеств зависит от того, как множества объединяются. Оказывается, что можно следовать такой простой стратегии: всегда соединять представителя меньшего множества с представителем большего (если размеры множеств одинаковы, то выбор произволен). При такой стратегии длина любого пути будет иметь порядок O(log n), так что мы сможем эффективно найти представителя любого эле- мента, проследовав по соответствующему пути. Реализация. Систему непересекающихся множеств удобно реализовать с помощью массивов. Для каждого элемента в массиве link хранится сле- дующий элемент пути или сам этот элемент, если он является представи- телем, а в массиве size для каждого представителя хранится размер соот- ветствующего множества. Вначале каждое множество состоит из одного элемента: for (int i = 1; i <= n; i++) link[i] = i; for (int i = 1; i <= n; i++) size[i] = 1; Функция find возвращает представителя элемента x. Его можно найти, проследовав по пути, начинающемуся в x. int find(int x) { while (x != link[x]) x = link[x]; return x; } Функция same проверяет, принадлежат ли элементы a и b одному мно- жеству. Это легко сделать, воспользовавшись функцией find : 130 Глава 7. Алгоритмы на графах bool same(int a, int b) { return find(a) == find(b); } Функция unite объединяет множества, содержащие элементы a и b (они должны принадлежать разным множествам). Сначала функция находит представителей множеств, а затем соединяет представителя меньшего множества с представителем большего. void unite(int a, int b) { a = find(a); b = find(b); if (size[a] < size[b]) swap(a,b); size[a] += size[b]; link[b] = a; } Временная сложность функции find равна O(log n)в предположении, что длина каждого пути равна O(log n). В этом случае функции same и unite также работают за время O(log n). Функция unite гарантирует, что длина каждого пути будет иметь порядок O(log n), поскольку соединяет меньшее множество с большим. Сжатие путей. Функцию find можно реализовать и по-другому: int find(int x) { if (x == link[x]) return x; return link[x] = find(link[x]); } В этой функции используется сжатие путей: после выполнения опе- рации каждый элемент, находящийся на пути, указывает непосредст- венно на своего представителя. Можно показать, что при такой реали- зации find амортизированное время выполнения операций системы непересекающихся множеств имеет порядок O( α(n)), где α(n)– обратная функция Аккермана, которая растет очень медленно (почти постоянна). Однако сжатие путей нельзя использовать в некоторых приложениях систе мы непересекающихся множеств, например в задаче о динамической связности (раздел 15.5.4). 7.6.3. Алгоритм Прима Алгоритм Прима дает другой способ построения минимального остов- ного дерева. Сначала он добавляет в дерево произвольную вершину, а при добавлении каждой следующей вершины выбирает ребро с минимальным весом. После того как все вершины добавлены, минимальное остовное де- рево построено. 7.6. Минимальные остовные деревья 131 Алгоритм Прима напоминает алгоритм Дейкстры. Разница в том, что алгоритм Дейкстры всегда выбирает вершину с минимальным расстояни- ем от начальной вершины, а алгоритм Прима выбирает для добавления в дерево вершину, принадлежащую ребру с минимальным весом. На рис. 7.43 показано, как алгоритм Прима строит минимальное остов- ное дерево для рассмотренного выше графа, начиная с вершины 1. Как и алгоритм Дейкстры, алгоритм Прима можно эффективно реализовать с помощью очереди с приоритетом. Очередь должна содержать все верши- ны, которые можно соединить с уже построенной частью дерева одним ребром, причем эти вершины должны храниться в порядке возрастания весов соответствующих ребер. 1 2 3 4 5 6 Шаг 1 1 2 3 4 5 6 3 Шаг 2 1 2 3 4 5 6 3 5 Шаг 3 1 2 3 4 5 6 3 5 3 Шаг 4 1 2 3 4 5 6 3 5 2 3 Шаг 5 1 2 3 4 5 6 3 5 2 7 3 Шаг 6 Рис. 7.43. Алгоритм Прима Временная сложность алгоритма Прима равна O(n + m log m), т. е. такая же, как у алгоритма Дейкстры. На практике алгоритмы Прима и Краскала одинаково эффективны, так что выбор между ними – дело вкуса. Тем не менее на олимпиадах чаще выбирают алгоритм Краскала. |