анти. Guide to Competitive
 Скачать 2.39 Mb.
|
|
Глава 7 Алгоритмы на графах Многие программистские задачи можно решить, если рассмотреть ситуа- цию как граф и воспользоваться подходящим алгоритмом. В этой главе мы познакомимся с основами теории графов и некоторыми важными ал- горитмами на графах. В разделе 7.1 обсуждается терминология теории графов и структуры данных, используемая для представления графов. В разделе 7.2 описаны два фундаментальных алгоритма обхода графа. Поиск в глубину – это простой способ посетить все вершины, достижимые из начальной, а при поиске в ширину вершины посещаются в порядке воз- растания расстояния от начальной вершины. В разделе 7.3 представлены алгоритмы нахождения кратчайших пу- тей во взвешенных графах. Простой алгоритм Беллмана–Форда находит кратчайшие пути от начальной вершины ко всем остальным. Алгоритм Дейкст ры более эффективен, но требуется, чтобы веса всех ребер были неотрицательны. Алгоритм Флойда–Уоршелла находит кратчайшие пути между всеми парами вершин. В разделе 7.4 изучаются специальные свойства ориентированных ациклических графов. Мы узнаем, как выполнить топологическую сорти- ровку и как эффективно обрабатывать такие графы с помощью динамичес- кого программирования. Раздел 7.5 посвящен графам, в которых у каждой вершины имеется един- ственная вершина-преемник. Мы обсудим эффективный способ нахожде- ния вершин-преемников и алгоритм Флойда нахождения циклов в графе. В разделе 7.6 изложены алгоритмы Краскала и Прима для построения минимальных остовных деревьев. Алгоритм Краскала основан на эффек- тивной структуре данных – системе непересекающихся множеств, которая имеет и другие применения в проектировании алгоритмов. 7.1. Основы теории графов В этом разделе мы введем терминологию, которая используется при об- суждении графов и их свойств. А затем займемся структурами данных для представления графов при программировании алгоритмов. 102 Глава 7. Алгоритмы на графах 7.1.1.Терминология Граф состоит из вершин, соединенных ребрами. Мы будем обозначать буквой n количество вершин графа, а буквой m – количество ребер. Ребра нумеруются числами 1, 2, . . . , n. На рис. 7.1 изображен граф с 5 вершинами и 7 ребрами. 1 2 3 4 5 Рис. 7.1. Граф с 5 вершинами и 7 ребрами Путь ведет из одной вершины в другую и проходит по ребрам графа. Длиной пути называется количество ребер в нем. На рис. 7.2 показан путь 1 → 3 → 4 → 5 длины 3 из вершины 1 в вершину 5. Циклом называется путь, в котором последняя вершина совпадает с первой. На рис. 7.3 изображен цикл 1 → 3 → 4 → 1. 1 2 3 4 5 1 2 3 4 5 Рис. 7.2. Путь из вершины 1 в вершину 5 Рис. 7.3. Цикл с тремя вершинами Граф называется связным, если между любыми двумя вершинами сущест- вует путь. Левый граф на рис. 7.4 связный, а правый – нет, потому что из вершины 4 нельзя попасть ни в какую другую. 1 2 3 4 1 2 3 4 Рис. 7.4. Левый граф связный, правый – нет Связные части графа называются его компонентами связности. Граф на рис. 7.5 состоит из трех компонент связности: {1, 2, 3}, {4, 5, 6, 7} и {8}. 1 2 3 6 7 4 5 8 Рис. 7.5. Граф с тремя компонентами связности 7.1. Основы теории графов 103 Деревом называется связный граф без циклов. На рис. 7.6 приведен при- мер дерева. 1 2 3 4 5 Рис. 7.6. Дерево В ориентированном графе по каждому ребру можно проходить только в одном направлении. На рис. 7.7 показан пример ориентированного графа. В нем имеется путь 3 → 1 → 2 → 5 из вершины 3 в вершину 5, но не сущест- вует пути из вершины 5 в вершину 3. 1 2 3 4 5 Рис. 7.7. Ориентированный граф Во взвешенном графе каждому ребру сопоставлен вес. Часто веса интер- претируются как длины ребер, а длиной пути считается сумма весов со- ставляющих его ребер. На рис. 7.8 изображен взвешенный граф, длина пути 1 → 3 → 4 → 5 равна 1 + 7 + 3 = 11. Это кратчайший путь из вершины 1 в вершину 5. 1 2 3 4 5 5 1 7 6 7 3 Рис. 7.8. Взвешенный граф Две вершины называются соседними, или смежными, если они соедине- ны ребром. Степенью вершины называется число соседних с ней вершин. На рис. 7.9 показаны степени всех вершин графа. Так, степень вершины 2 равна 3, потому что ее соседями являются вершины 1, 4 и 5. 1 2 3 4 5 2 3 3 3 1 Рис. 7.9. Степени вершин 104 Глава 7. Алгоритмы на графах Сумма степеней всех вершин графа равна 2m, где m – число ребер, по- скольку каждое ребро увеличивает степени ровно двух вершин на едини- цу. Таким образом, сумма степеней вершин всегда четна. Граф называется регулярным, если степени всех его вершин одинаковы (равны некоторой константе d). Граф называется полным, если степень каждой его вершины равна n − 1, т. е. в графе присутствуют все возможные ребра. В ориентированном графе полустепенью захода вершины называется число ребер, оканчивающихся в этой вершине, а полустепенью исхода – число ребер, начинающихся в вершине. На рис. 7.10 показаны полустепе- ни захода и исхода для каждой вершины графа. Например, для вершины 2 полустепень захода равна 2, а полустепень исхода – 1. 1 2 3 4 5 1 /1 3 /0 0 /3 2 /1 0 /1 Рис. 7.10. Полустепени захода и исхода Граф называется двудольным, если его вершины можно раскрасить в два цвета, так что цвета любых двух соседних вершин различны. Можно дока- зать, что граф является двудольным тогда и только тогда, когда в нем нет цикла с нечетным числом вершин. На рис. 7.11 изображены двудольный граф и его раскраска. 2 3 5 6 4 1 2 3 5 6 4 1 Рис. 7.11. Двудольный граф и его раскраска 7.1.2. Представление графа Есть несколько способов представить граф в алгоритмах. Выбор структу- ры данных зависит от размера графа и способа его обработки в алгоритме. Ниже рассмотрены три популярных представления. 7.1. Основы теории графов 105 Списки смежности. В этом случае каждой вершине x сопоставляется список смежности, включающий вершины, соединенные с x ребром. Спис- ки смежности – самый популярный способ представления графов, они по- зволяют эффективно реализовать большинство алгоритмов. Списки смежности удобно хранить в массиве векторов, который объяв- лен следующим образом: vector<int> adj[N]; Константа N выбрана так, чтобы в массиве поместились все списки смежности. Например, граф на рис. 7.12 (a) можно сохранить так: adj[1].push_back(2); adj[2].push_back(3); adj[2].push_back(4); adj[3].push_back(4); adj[4].push_back(1); Неориентированные графы можно хранить аналогично, только каждое ребро нужно учитывать в двух списках смежности (для обоих направле- ний). Для взвешенных графов структуру следует дополнить: vector int,int>> adj[N]; В этом случае список смежности вершины a содержит пару (b,w), если существует ребро с весом w, направленное от a к b. Граф на рис. 7.12 (b) можно сохранить следующим образом: adj[1].push_back({2,5}); adj[2].push_back({3,7}); adj[2].push_back({4,6}); adj[3].push_back({4,5}); adj[4].push_back({1,2}); 1 2 3 4 (a) 1 2 3 4 5 7 6 5 2 (b) Рис. 7.12. Примеры графов Списки смежности позволяют эффективно находить вершины, в кото- рые можно перейти из данной по одному ребру. Следующий цикл обходит все вершины, в которые можно попасть из вершины s: 106 Глава 7. Алгоритмы на графах for (auto u : adj[s]) { // обработать вершину u } Матрица смежности показывает, какие ребра есть в графе. С ее по- мощью можно эффективно проверить, существует ли ребро между двумя вершинами. Матрицу можно хранить в виде массива int adj[N][N]; где элемент adj [a ][b] равен 1, если существует ребро, ведущее из верши- ны a в вершину b, а в противном случае равен 0. Так, матрица смежности для графа на рис. 7.12 (a) имеет вид: 0 1 0 0 0 0 1 1 0 0 0 1 1 0 0 0 Если граф взвешенный, то представление в виде матрицы смежности можно обобщить: если две вершины соединены ребром, то в матрице хра- нится вес этого ребра. Так, граф на рис. 7.12 (b) представляется следующей матрицей: 0 5 0 0 0 0 7 6 0 0 0 5 2 0 0 0 Недостаток матрицы смежности заключается в том, что она содержит n 2 элементов, большая часть которых обычно равна 0. Поэтому такое пред- ставление не годится для больших графов. Список ребер содержит все ребра графа в некотором порядке. Это пред- ставление удобно, если алгоритм обрабатывает все ребра и не требуется находить ребра, начинающиеся в заданной вершине. Список ребер можно хранить в векторе vector int,int>> edges; где наличие пары (a, b) означает, что существует ребро из вершины a в вершину b. Граф на рис. 7.12 (a) можно представить следующим образом: edges.push_back({1,2}); edges.push_back({2,3}); 7.2. Обход графа 107 edges.push_back({2,4}); edges.push_back({3,4}); edges.push_back({4,1}); Для взвешенных графов структуру можно обобщить: vector Каждый элемент этого списка имеет вид (a,b,w), это означает, что су- ществует ребро с весом w, ведущее из вершины a в вершину b. Например, граф на рис. 7.12 (b) можно представить следующим образом 1 : edges.push_back({1,2,5}); edges.push_back({2,3,7}); edges.push_back({2,4,6}); edges.push_back({3,4,5}); edges.push_back({4,1,2}); 7.2. Обход графа В этом разделе обсуждается два фундаментальных алгоритма на графах: поиск в глубину и поиск в ширину. В обоих случаях задается начальная вершина и ставится задача посетить все достижимые из нее вершины. Различие заключается в порядке посещения вершин. 7.2.1. Поиск в глубину Поиск в глубину (depth-first search – DFS) – прямолинейный способ обхо- да графа. Алгоритм начинает работу в начальной вершине и перебирает все вершины, достижимые из нее по ребрам графа. Поиск в глубину всегда следует по одному пути, пока на нем еще имеют- ся вершины. После этого он возвращается назад и начинает исследовать другие части графа. Алгоритм запоминает посещенные вершины, так что каждая обрабатывается только один раз. На рис. 7.13 показан порядок обработки вершин при поиске в глубину. Поиск может начинаться с любой вершины: в данном случае мы начали с вершины 1. Сначала исследуется путь 1 → 2 → 3 → 5, затем алгоритм воз- вращается к вершине 1 и посещает оставшуюся вершину 4. Реализация. Поиск в глубину удобно реализовать рекурсивно. Показан- ная ниже функция dfs начинает поиск с заданной вершины. Предполага- ется, что граф представлен списками смежности, хранящимися в массиве vector<int> adj[N]; 1 В некоторых старых компиляторах вместо фигурных скобок следует использовать функцию make_tuple (например, make_tuple(1,2,5), а не {1,2,5}). 108 Глава 7. Алгоритмы на графах 1 2 3 4 5 Шаг 1 1 2 3 4 5 Шаг 2 1 2 3 4 5 Шаг 3 1 2 3 4 5 Шаг 4 1 2 3 4 5 Шаг 5 1 2 3 4 5 Шаг 6 1 2 3 4 5 Шаг 7 1 2 3 4 5 Шаг 8 Рис. 7.13. Поиск в глубину Кроме того, используется массив bool visited[N]; в котором запоминаются посещенные вершины. В начальный момент все элементы этого массива равны false , но когда алгоритм заходит в верши- ну s, в элемент visited [ s] записывается true . Функцию можно реализовать следующим образом: void dfs(int s) { if (visited[s]) return; visited[s] = true; // обработать вершину s for (auto u: adj[s]) { dfs(u); } } Временная сложность поиска в глубину равна O(n + m), где n – число вершин, а m – число ребер, поскольку алгоритм обрабатывает каждую вер- шину и каждое ребро ровно один раз. 7.2. Обход графа 109 7.2.2. Поиск в ширину При поиске в ширину (breadth-first search – BFS) вершины графа посеща- ются в порядке возрастания расстояния от начальной вершины. Следова- тельно, используя поиск в ширину, мы сможем вычислить расстояния от начальной вершины до всех остальных. Однако реализовать поиск в ши- рину труднее, чем поиск в глубину. В процессе поиска в ширину мы обходим вершины уровень за уровнем. Сначала посещаются вершины, отстоящие от начальной на расстояние 1, затем – на расстояние 2 и т. д. Процесс продолжается, пока не останется непосещенных вершин. На рис. 7.14 показано, как происходит обход графа при поиске в ширину. Предположим, что поиск начинается с вершины 1. Сначала мы посещаем вершины 2 и 4, удаленные на расстояние 1, затем – вершины 3 и 5, удален- ные на расстояние 2, и, наконец, вершину 6, удаленную на расстояние 3. 1 2 3 4 5 6 Шаг 1 1 2 3 4 5 6 Шаг 2 1 2 3 4 5 6 Шаг 3 1 2 3 4 5 6 Шаг 4 Рис. 7.14. Поиск в ширину Реализация. Поиск в ширину труднее реализовать, чем поиск в глуби- ну, потому что алгоритм посещает вершины, находящиеся в разных час- тях графа. Типичная реализация основана на очереди вершин. На каждом шаге обрабатывается следующий узел из очереди. В приведенном ниже коде предполагается, что граф представлен спис- ками смежности и что определены следующие структуры данных: queue<int> q; bool visited[N]; int distance[N]; Очередь q содержит вершины, подлежащие обработке в порядке воз- растания расстояния. Новые вершины добавляются в конец очереди, а об- рабатывается вершина, находящаяся в начале очереди. В массиве visited хранится информация о том, какие вершины уже посещались, а в массиве 110 Глава 7. Алгоритмы на графах distance – расстояния от начальной вершины до всех остальных вершин графа. Поиск, начинающийся в вершине x, реализуется следующим образом: visited[x] = true; distance[x] = 0; q.push(x); while (!q.empty()) { int s = q.front(); q.pop(); // обработать вершину s for (auto u : adj[s]) { if (visited[u]) continue; visited[u] = true; distance[u] = distance[s]+1; q.push(u); } } Временная сложность поиска в ширину, как и поиска в глубину, равна O(n+m), где n – число вершин, а m – число ребер. 7.2.3. Применения С помощью алгоритмов обхода мы можем проверить многие свойства графа. Обычно применимы как поиск в глубину, так и поиск в ширину, но на практике поиск в глубину предпочтительнее, потому что он проще реализуется. В описываемых ниже применениях предполагается, что граф неориентированный. Проверка связности. Граф называется связным, если между любыми двумя вершинами существует путь. Следовательно, для проверки связно- сти мы можем начать с произвольной вершины и выяснить, все ли верши- ны достижимы из нее. На рис. 7.15 видно, что поиск в глубину, начатый из вершины 1, не по- сещает все вершины, поэтому можно заключить, что граф не связный. Можно также найти все компоненты графа: для этого нужно перебрать все вершины и начинать новый поиск в глубину, если текущая вершина не принадлежит ни одной из уже найденных компонент связности. Обнаружение циклов. Граф содержит цикл, если в процессе обхода мы встречаем такую вершину, что одна из соседних с ней (кроме той, что предшествует ей на текущем пути) уже посещалась. На рис. 7.16 поиск в глубину из вершины 1 обнаруживает, что в графе имеется цикл. При пе- реходе из вершины 2 в вершину 5 мы видим, что соседняя с 5 вершина 3 уже посещалась. Следовательно, граф содержит цикл, проходящий через вершину 3, например 3 → 2 → 5 → 3. 7.3. Кратчайшие пути 111 2 1 3 5 4 2 1 3 5 4 Рис. 7.15. Проверка связности графа Рис. 7.16. Нахождение цикла в графе Есть и другой способ узнать, содержит ли граф цикл: просто посчитать количество вершин и ребер в каждой компоненте. Если компонента содер- жит c вершин и ни одного цикла, то в ней должно быть ровно c − 1 ребер (т. е. она должна быть деревом). Если число ребер равно c или больше, то компонента обязательно содержит цикл. Проверка на двудольность. Граф называется двудольным, если его вершины можно раскрасить двумя цветами, так что никакие две сосед- ние вершины не будут окрашены одним цветом. Удивительно, как просто можно проверить граф на двудольность с помощью алгоритмов обхода. Идея в том, чтобы выбрать два цвета X и Y, окрасить начальную верши- ну цветом X, всех ее соседей – цветом Y, всех их соседей – цветом X и т. д. Если в какой-то момент мы обнаруживаем, что две соседние вершины окрашены одним цветом, значит, граф не является двудольным. В против- ном случае граф двудольный, и мы нашли дока- зывающую это раскраску. Поиск в глубину из вершины 1 показывает, что граф на рис. 7.17 не является двудольным, т. к. вершины 2 и 5 окрашены одним цветом, хотя и являются соседними. Этот алгоритм корректен, потому что при наличии всего двух цветов цвет начальной вершины однозначно определяет цвета всех остальных вершин, принадлежащих той же компоненте связности. Отметим, что в общем случае трудно определить, можно ли раскра- сить вершины графа в k цветов, так чтобы никакие две соседние вер- шины не были окрашены одним цветом. Для k = 3 эта задача является NP-трудной. |