Посетить все вершины графа
Существует ряд задач, где нужно обойти некоторый граф в глубину или в ширину, так, чтобы посетить каждую вершину один раз. При этом посетить вершины дерева означает выполнить какую-то операцию. Обход графа — это поэтапное исследование всех вершин графа.
Для решения таких задач используются два основных алгоритма : поиск в глубину (depth-first search или DFS) и поиск в ширину (breadth-first search или BFS).
Алгоритм поиска в глубину
1. Двигаемся из начальной вершины.
2. Движемся в произвольную смежную вершину.
3. Из этой вершины обходим все возможные пути до смежных вершин.
4. Если таких путей нет или мы не достигли конечной вершины, то возвращаемся назад к вершине с несколькими исходящими ребрами и идем по другому пути.
5. Алгоритм повторяется, пока не будут исследованы все вершины и достигнута конечная вершина.
Рассмотрим реализацию алгоритма поиска в глубину на следующем ориентированном графе на рисунке \(1\).
Рис. \(1\). Ориентированный граф
Реализация алгоритма на графе
Описание шагов алгоритма
Алгоритм поиска в ширину
1. Двигаемся из начальной вершины.
2. Движемся по ребрам, исходящим из начальной вершины, и по очереди исследуем смежные с ней вершины.
3. Если эти вершины не являются конечными или целевыми, движемся по ребрам, которые исходят из вершин, смежных с начальной.
4. По очереди исследуем вершины этого "уровня". Если эти вершины не являются конечными или целевыми, движемся дальше на следующий уровень по ребрам, которые исходят из этих вершин.
5. Алгоритм повторяется, пока не будут исследованы все вершины и достигнута конечная целевая вершина.
Рассмотрим реализацию алгоритма поиска в ширину для того же самого ориентированного графа на рисунке \(1\).
Реализация алгоритма на графе
Описание шагов алгоритма
Из начальной вершины\( 1\) исходит два ребра к двум смежным вершинам \(2\) и \(6\).
Рассмотрим их по очереди. Вершина \(2\) не является конечной, так как из нее исходит три ребра. Вершина \(6\) не является конечной, так как из нее исходит одно ребро.
Вершины исследованы и не являются конечными. Движемся дальше
Из вершины \(2\) исходит три ребра к смежным вершинам \(3\), \(4\) и \(7\). Исследуем их. Вершина \(3\) не является конечной, так как из нее исходит одно ребро. Вершина \(4\) является конечной, но не целевой. Вершина \(7\) тоже является конечной, но не целевой.
Вершины исследованы и не являются целевыми, которые требовалось достичь. Движемся дальше
Восстановление пути
Восстановление пути в алгоритме Дейкстры делается аналогично восстановлению пути в BFS (и любой динамике).
Как оптимально обойти все вершины графа?
Нужно обойти все вершины неориентированного связного графа, точечно перемещаясь по ребрам. Граф - произвольный (не Эйлеров и не Гамильтонов, кроме связности ничего не дано). Переход по ребру - один шаг. Как сделать это за минимальное число шагов? Возвращаться в исходную вершину, как в задаче с коммивояжером не обязательно главное посетить каждую вершину хотя бы раз.
Решения вопроса 0
Ответы на вопрос 3
Я есть на хабре
Очевидно, с помощью обходов графа.
Какой из алгоритмов лучше использовать и какие модификации можно внести - зависит уже от конкретных особенностей графа, то есть у произвольного заранее неизвестно, какая вариация окажется самой оптимальной.
Если возможно, то нужно собрать статистику и посмотреть на возможные особенности обрабатываемых графов. Так, например, для "звезд" будет оптимальным обход центра с BFS, после чего обработка лучей с помощью DFS.
Ответ написан более трёх лет назад
Risent Veber @risentveber Автор вопроса
Смотри какая тема - есть лабиринт с монетками как оптимально обойти его за минимальное число шагов(лабиринт - не дерево!) - точка старта - зафиксирована
Risent Veber @risentveber Автор вопроса
Я думал построить минимальное остовое дерево с помощью алгоритма Крускала - и потом на нем сделать обход в глубину, но не думаю что это самое оптимальное решение.
Risent Veber: если вся структура лабиринта заранее неизвестна - то его лучше обходить с помощью обхода в ширину - он гарантирует нахождение самого оптимального пути и сам является оптимальным. Для использования с монетками можно попробовать манипулировать с длинами ребер, ведущим к ним, при инициализации графа.
Более оптимальным кажется подход с последовательным использованием алгоритмов A* и B*: отправной точкой является старт, а целями монетки, при этом, после нахождения каждой монетки, алгоритм запускается заново, используя в качестве старта позицию последней найденной монеты.
Реализация BFS с восстановлением пути
Неориентированные графы
Если дан неориентированный граф, его можно рассматривать как ориентированный граф с двумя обратными друг другу ориентированными рёбрами.
Обход графа: поиск в глубину и поиск в ширину простыми словами на примере JavaScript
Простыми словами, обход графа — это переход от одной его вершины к другой в поисках свойств связей этих вершин. Связи (линии, соединяющие вершины) называются направлениями, путями, гранями или ребрами графа. Вершины графа также именуются узлами.
Двумя основными алгоритмами обхода графа являются поиск в глубину (Depth-First Search, DFS) и поиск в ширину (Breadth-First Search, BFS).
Несмотря на то, что оба алгоритма используются для обхода графа, они имеют некоторые отличия. Начнем с DFS.
Поиск в глубину
DFS следует концепции «погружайся глубже, головой вперед» («go deep, head first»). Идея заключается в том, что мы двигаемся от начальной вершины (точки, места) в определенном направлении (по определенному пути) до тех пор, пока не достигнем конца пути или пункта назначения (искомой вершины). Если мы достигли конца пути, но он не является пунктом назначения, то мы возвращаемся назад (к точке разветвления или расхождения путей) и идем по другому маршруту.
Давайте рассмотрим пример. Предположим, что у нас есть ориентированный граф, который выглядит так:
Мы находимся в точке «s» и нам нужно найти вершину «t». Применяя DFS, мы исследуем один из возможных путей, двигаемся по нему до конца и, если не обнаружили t, возвращаемся и исследуем другой путь. Вот как выглядит процесс:
Здесь мы двигаемся по пути (p1) к ближайшей вершине и видим, что это не конец пути. Поэтому мы переходим к следующей вершине.
Мы достигли конца p1, но не нашли t, поэтому возвращаемся в s и двигаемся по второму пути.
Достигнув ближайшей к точке «s» вершины пути «p2» мы видим три возможных направления для дальнейшего движения. Поскольку вершину, венчающую первое направление, мы уже посещали, то двигаемся по второму.
Мы вновь достигли конца пути, но не нашли t, поэтому возвращаемся назад. Следуем по третьему пути и, наконец, достигаем искомой вершины «t».
Так работает DFS. Двигаемся по определенному пути до конца. Если конец пути — это искомая вершина, мы закончили. Если нет, возвращаемся назад и двигаемся по другому пути до тех пор, пока не исследуем все варианты.
Мы следуем этому алгоритму применительно к каждой посещенной вершине.
Необходимость многократного повторения процедуры указывает на необходимость использования рекурсии для реализации алгоритма.
Заметка: этот специальный DFS-алгоритм позволяет проверить, возможно ли добраться из одного места в другое. DFS может использоваться в разных целях. От этих целей зависит то, как будет выглядеть сам алгоритм. Тем не менее, общая концепция выглядит именно так.
Анализ DFS
Давайте проанализируем этот алгоритм. Поскольку мы обходим каждого «соседа» каждого узла, игнорируя тех, которых посещали ранее, мы имеем время выполнения, равное O(V + E).
Краткое объяснение того, что означает V+E:
V — общее количество вершин. E — общее количество граней (ребер).
Может показаться, что правильнее использовать V*E, однако давайте подумаем, что означает V*E.
V*E означает, что применительно к каждой вершине, мы должны исследовать все грани графа безотносительно принадлежности этих граней конкретной вершине.
С другой стороны, V+E означает, что для каждой вершины мы оцениваем лишь примыкающие к ней грани. Возвращаясь к примеру, каждая вершина имеет определенное количество граней и, в худшем случае, мы обойдем все вершины (O(V)) и исследуем все грани (O(E)). Мы имеем V вершин и E граней, поэтому получаем V+E.
Далее, поскольку мы используем рекурсию для обхода каждой вершины, это означает, что используется стек (бесконечная рекурсия приводит к ошибке переполнения стека). Поэтому пространственная сложность составляет O(V).
Теперь рассмотрим BFS.
Поиск в ширину
BFS следует концепции «расширяйся, поднимаясь на высоту птичьего полета» («go wide, bird’s eye-view»). Вместо того, чтобы двигаться по определенному пути до конца, BFS предполагает движение вперед по одному соседу за раз. Это означает следующее:
Вместо следования по пути, BFS подразумевает посещение ближайших к s соседей за одно действие (шаг), затем посещение соседей соседей и так до тех пор, пока не будет обнаружено t.
Чем DFS отличается от BFS? Мне нравится думать, что DFS идет напролом, а BFS не торопится, а изучает все в пределах одного шага.
Далее возникает вопрос: как узнать, каких соседей следует посетить первыми?
Для этого мы можем воспользоваться концепцией «первым вошел, первым вышел» (first-in-first-out, FIFO) из очереди (queue). Мы помещаем в очередь сначала ближайшую к нам вершину, затем ее непосещенных соседей, и продолжаем этот процесс, пока очередь не опустеет или пока мы не найдем искомую вершину.
Анализ BFS
Может показаться, что BFS работает медленнее. Однако если внимательно присмотреться к визуализациям, можно увидеть, что они имеют одинаковое время выполнения.
Очередь предполагает обработку каждой вершины перед достижением пункта назначения. Это означает, что, в худшем случае, BFS исследует все вершины и грани.
Несмотря на то, что BFS может казаться медленнее, на самом деле он быстрее, поскольку при работе с большими графами обнаруживается, что DFS тратит много времени на следование по путям, которые в конечном счете оказываются ложными. BFS часто используется для нахождения кратчайшего пути между двумя вершинами.
Таким образом, время выполнения BFS также составляет O(V + E), а поскольку мы используем очередь, вмещающую все вершины, его пространственная сложность составляет O(V).
Аналогии из реальной жизни
Если приводить аналогии из реальной жизни, то вот как я представляю себе работу DFS и BFS.
Когда я думаю о DFS, то представляю себе мышь в лабиринте в поисках еды. Для того, чтобы попасть к цели мышь вынуждена много раз упираться в тупик, возвращаться и двигаться по другому пути, и так до тех пор, пока она не найдет выход из лабиринта или еду.
Упрощенная версия выглядит так:
В свою очередь, когда я думаю о BFS, то представляю себе круги на воде. Падение камня в воду приводит к распространению возмущения (кругов) во всех направлениях от центра.
Деревья
Дерево - это связный неориентированный граф без циклов.
Пример дерева
- У дерева с хотя бы 2 вершинами всегда есть висячая вершина - вершина степени 1.
Действительно, если начать из любой вершины идти по непосещенным ранее вершинам, то в какой-то момент мы прекратим это делать, ведь граф конечный. При этом если из этой вершины не может быть ребер в непосещенные вершины - ведь тогда прекращать рано, и не может быть ребер в посещенные ребра (помимо предыдущей) - ведь тогда есть цикл. А значит, есть ребро только в предыдущую вершину, значит степень равна 1.
- У дерева с хотя бы 2 вершинами всегда есть две висячие вершины.
Действительно, если предыдущий алгоритм начать из висячей вершины, то мы уткнемся в другую висячую вершину.
- У дерева с \(N\) вершинами всегда ровно \(N-1\) ребро.
Давайте отрезать от дерева его висячие вершины - при этом число вершин уменьшится на один, число ребер тоже уменьшится на один, а граф останется деревом. Раз граф остается деревом, у него все время будет висячая вершина, пока \(N > 1\) . В какой-то момент останется только одна вершина и ноль ребер. Раз мы отрезали столько же вершин, сколько ребер, и получили 1 вершину и 0 ребер, значит изначально вершин было ровно на одну больше.
- Между любыми двумя вершинами в дереве есть ровно один простой путь.
Действительно, если их два, то в графе есть цикл. Быть ноль их не может - ведь граф связный.
- Дерево - это минимальный по числу рёбер связный граф на \(N\) вершинах.
Действительно, если есть связный граф, в котором меньше, чем \(N-1\) ребро, то давайте уберем из его цикла ребро. Граф при этом остается связным, а число ребер уменьшается. Давайте повторять это, пока в какой-то момент циклов в графе не будет, а значит осталось дерево. Но мы уже доказали, что в дереве \(N-1\) ребро, это противоречие, ведь у нас сначала было меньше ребер, а мы еще и удалили сколько-то.
Поиск компонент связности графа
Путем в графе называется последовательность вершин \(v_i \in 𝑉\) , \(i = 1. k\) таких, что две последовательные вершины в пути соединены ребром, \(k\) - длина пути. Граф называется связным, если для любых двух его вершин существует путь между ними. Граф всегда можно разбить на непересекающиеся связные подмножества (возможно одно), между которыми рёбер нет, они называются компонентами связности.
Поиск в глубину dfs будет обходить ту компоненту связности, из вершины которой, он был вызван. Поэтому для поиска компонент связности можно каждый раз вызываться из любой непосещенной вершины и тогда в результате мы посетим все вершины, а следовательно и найдем все компоненты связности.
Практическое задание
На данную тему задачи 6 и 10 в контесте.
Графы — определения, деревья, хранение и поиск в глубину
Графом \(G\) называется пара множеств \(G = (V, E\) , где \(V(G)\) — непустое конечное множество элементов, называемых вершинами графа, а \(E\) — множество пар элементов из \(V\) (необязательно различных), называемых ребрами графа. \(E = \<(u , v)\ | u, v \in V\>\) — множество ребер графа \(G\) , состоящее из пар вершин \((u, v)\) . Ребро \((u, v)\) соединяет вершины \(u\) и \(v\) .
Граф - это набор вершин (точек) и соединяющих их отрезков (рёбер).
Примеры графа
Две вершины, соединенные ребром, называют смежными вершинами. Обычно в задачах \(N\) - количество вершин, а \(M\) - ребер. Количество ребер, исходящее из вершины называют степенью вершины \(d(v)\) . Для вершины \(a\) ребро \((a, b)\) называется инцидентным ей. На рисунке ниже вершине 8 инцидентно только ребро (4, 8), а вершине 10 ребра (2, 10) и (5, 10).
Теоретическое задание
Назовите степень 1-ой и 6-ой вершины и какие ребра инциденты им.
Если какие-то две вершины соединены более, чем одним ребром, то говорят, что граф содержит кратные ребра. Если ребро соединяет вершину саму с собой, то такое ребро называют петлей.
Простой граф не содержит петель и кратных ребер. Если не сказано ничего про наличие петель и кратных ребер, мы будем всегда считать, что граф простой.
Теоретическое задание
Сколько может быть рёбер в простом графе в \(N\) вершинами?
Теоретическое задание
Найдите цикл размера 4 и петлю в этом непростом графе.
Также часто рассматривают ориентированные графы — это графы, у которых ребра имеют направление, а иначе граф – неориентированный.
Кратчайший цикл в ориентированном графе
Найти цикл минимальной длины в ориентированном графе.
Попытаемся из каждой вершины найти кратчайший цикл, проходящий через неё, с помощью BFS. Это делается аналогично обычному BFS: мы должны найти расстояний от вершины до самой себя, при этом не считая, что оно равно \(0\) .
Итого, у нас \(|V|\) запусков BFS, и каждый запуск работает за \(O(|V| + |E|)\) . Тогда общее время работы составляет \(O(|V|^2 + |V| |E|)\) . Если инициализировать массив \(dist\) единожды, а после каждого запуска BFS возвращать исходные значения только для достижимых вершин, решение будет работать за \(O(|V||E|)\) .
Кратчайшие пути в графах. BFS. Dijkstra.
Дан ориентированный граф \(G = (V, E)\) , а также вершина \(s\) .
Найти длину кратчайшего пути от \(s\) до каждой из вершин графа. Длина пути — количество рёбер в нём.
BFS — breadth-first search, или же поиск в ширину.
Этот алгоритм позволяет решать следующую задачу.
Алгоритм работает следующим образом.
- Создадим массив \(dist\) расстояний. Изначально \(dist[s] = 0\) (поскольку расстояний от вершины до самой себя равно \(0\) ) и \(dist[v] = \infty\) для \(v \neq s\) .
- Создадим очередь \(q\) . Изначально в \(q\) добавим вершину \(s\) .
- Пока очередь \(q\) непуста, делаем следующее:
- Извлекаем вершину \(v\) из очереди.
- Рассматриваем все рёбра \((v, u) \in E\) . Для каждого такого ребра пытаемся сделать релаксацию: если \(dist[v] + 1 < dist[u]\) , то мы делаем присвоение \(dist[u] = dist[v] + 1\) и добавляем вершину \(u\) в очередь.
Хранение графа в программе
Чаще всего в задачах по программмированию вершины графа - это числа от \(0\) до \(N-1\) , чтобы удобно было обращаться к ним как к индексам в разных массивах.
Также чаще всего вам дают считать граф как просто список всех рёбер в нем (но не всегда, конечно). Как оптимально считать и сохранить граф? Есть 3 способа.
Для графа существуют несколько основных способов хранения:
- Матрица смежности. Давайте хранить двумерную матрицу \(A_\) , где для данного графа G верно, что если \(A_\) = 1, то две вершины \(i\) и \(j\) являются смежными, иначе вершины \(i\) и \(j\) смежными не являются.
Мы храним для каждой из \(N\) вершин информацию, есть ли ребро в другие вершины, то есть суммарно мы храним \(N^2\) ячеек, а следовательно асимптотика по памяти - \(O(N^2)\) .
- Список смежности. Давайте для каждой из \(N\) вершин хранить все смежные с ней, для этого нам потребуется любая динамическая структура, например vector в с++.
Здесь асимптотика по памяти и времени считывания - \(O(N + M)\) , так как мы храним для каждой вершины, куда есть ребра, то есть \(2 M\) ребер, а также суммарно \(N\) векторов.
Плотные графы, имеющие большое количество ребер следует хранить при помощи матрицы смежности, а разреженные графы, имеющие малое количество ребер, оптимальнее при помощи списка.
- Список рёбер. Иногда граф явно вообще не требуется, а хватает хранить просто список ребер, который нам дают на вход.
Заметьте, что все эти способы обощаются на случай ориентированных графов - при этом матрица смежности становится неориетированной: если есть ребро из вершины \(i\) в вершину \(j\) , то сделаем \(A_ = 1\) , а \(A_ = 0\) , если только нет обратного ребра тоже. А в списке смежности в ориентированном случае при считывании ребра \((u, v)\) будем добавлять только \(v\) в список соседей \(u\) , но не наоборот.
Практическое задание
Для окончательного закрепления темы советую решить первые 2 задачи.
Алгоритм Дейкстры
Алгоритм Дейкстры решает приведённую выше задачу. Он работает следующим образом.
- Создать массив \(dist\) расстояний. Изначально \(dist[s] = 0\) и \(dist[v] = \infty\) для \(v \neq s\) .
- Создать булёв массив \(used\) , \(used[v] = 0\) для всех вершин \(v\) — в нём мы будем отмечать, совершалась ли релаксация из вершины.
- Пока существует вершина \(v\) такая, что \(used[v] = 0\) и \(dist[v] \neq \infty\) , притом, если таких вершин несколько, то \(v\) — вершина с минимальным \(dist[v]\) , делать следующее:
- Пометить, что мы совершали релаксацию из вершины \(v\) , то есть присвоить \(used[v] = 1\) .
- Рассматриваем все рёбра \((v, u) \in E\) . Для каждого ребра пытаемся сделать релаксацию: если \(dist[v] + w(v, u) < dist[u]\) , присвоить \(dist[u] = dist[v] + w(v, u)\) .
Иными словами, алгоритм на каждом шаге находит вершину, до которой расстояние сейчас минимально и из которой ещё не была произведена релаксация, и делает её.
Посчитаем, за сколько работает алгоритм. Мы \(V\) раз ищем вершину минимальным \(dist\) , поиск минимума у нас линейный за \(O(V)\) , отсюда \(O(V^2)\) . Обработка ребер у нас происходит суммарно за \(O(E)\) , потому что на каждое ребро мы тратим \(O(1)\) действий. Так мы находим финальную асимптотику: \(O(V^2 + E)\) .
10 алгоритмов на графах в гифках
Подборка алгоритмов обхода графа с gif-анимациями и объяснениями. Статья поможет ознакомиться и разобраться с различными методами, которые используются в теории графов.
Интуитивное понимание алгоритма
Можно представить, что мы поджигаем вершину \(s\) . Каждый шаг алгоритма — это распространение огня на соседние вершины. Понятно, что огонь доберётся до вершины по кратчайшему пути.
Заметьте, что этот алгоритм очень похож на DFS — достаточно заменить очередь на стек и поиск в ширину станет поиском в глубину. Действительно, оба алгоритма при обработке вершины просто записывают всех непосещенных соседей, в которые из неё есть ребро, в структуру данных, и после этого выбирает следующую вершину для обработки в структуре данных. В DFS это стек (благодаря рекурсии), поэтому мы сначала записываем соседа, идем в обрабатываем его полностью, а потом начинаем обрабатывать следующего соседа. В BFS это очередь, поэтому мы кидаем сразу всех соседей, а потом начинаем обрабатывать вообще другую вершину - ту непосещенную, которую мы положили в очередь раньше всего.
Оба алгоритма позволяют обойти граф целиком - посетить каждую вершину ровно один раз. Поэтому они оба подходят для таких задач как: * поиск компонент связности * проверка графа на двудольность * построение остова
BFS (Kahn’s algorithm)
Алгоритм основывается на выборе вершин в порядке, подобном топологической сортировке. Сначала находим список начальных вершин, которые не имеют входящих граней, и помещаем их в множество S. В непустом ациклическом графе должна существовать хотя бы одна такая вершина.
После этого количество посещённых вершин увеличивается на 1, а степень всех соседних вершин уменьшается на 1. Если после этого степень соседних вершин обнулится, они помещаются в очередь. Этот шаг будет повторяться, пока очередь не опустеет. Если в итоге количество посещенных вершин не будет равно числу вершин на графе, то сортировка невозможна.Свойства кратчайших путей
Обозначение: \(d(v)\) — длина кратчайшего пути от \(s\) до \(v\) .
Лемма 1. > Пусть \((u, v) \in E\) , тогда \(d(v) \leq d(u) + 1\) .
Действительно, существует путь из \(s\) в \(u\) длины \(d(u)\) , а также есть ребро \((u, v)\) , следовательно, существует путь из \(s\) в \(v\) длины \(d(u) + 1\) . А значит кратчайший путь из \(s\) в \(v\) имеет длину не более \(d(u) + 1\) ,
Лемма 2. > Рассмотрим кратчайший путь от \(s\) до \(v\) . Обозначим его как \(u_1, u_2, \dots u_k\) ( \(u_1 = s\) и \(u_k = v\) , а также \(k = d(v) + 1\) ).
> Тогда \(\forall (i < k): d(u_i) + 1 = d(u_)\) .Действительно, пусть для какого-то \(i < k\) это не так. Тогда, используя лемму 1, имеем: \(d(u_i) + 1 > d(u_)\) . Тогда мы можем заменить первые \(i + 1\) вершин пути на вершины из кратчайшего пути из \(s\) в \(u_\) . Полученный путь стал короче, но мы рассматривали кратчайший путь — противоречие.
DFS (Алгоритм обхода графа в глубину)
Обход в глубину — простой, но многофункциональный алгоритм обхода графа по ребрам. Самое главное, что он может — это проверить, какие вершины достижимы из данной.
При обходе графа мы используем вспомогательный массив used, в котором храним 1, если вершина была посещена или 0 иначе. В начале мы считаем, что все вершины не использовались, затем мы выбираем одну вершину, помечаем ее посещенной и запускаемся рекурсивно из всех ее соседей, тогда мы посетим все вершины, которые достижимы из данной, если же остались вершины с used = 0 значит они недостижимы.
Давайте оценим сложность алгоритма. Так как мы проверяем, что вершина еще не использовалась, то всего мы пройдет каждую вершину 1 раз, но при этом и ребро между двумя вершинами, мы рассматриваем только когда рассматривается один конец, то есть мы просмотрим каждое ребро не более одного раза, суммарно получаем оценку \(O(N + M)\) .
Практическое задание
Задачи 3-5 в контесте.
Depth-First Search(s) - Поиск в глубину
Из названия этого метода обхода графа ясно, что в процессе поиска мы идем «вглубь» графа настолько, насколько возможно. Следуя алгоритму, мы последовательно обойдем все вершины графа, которые доступны из начальной вершины. Если ребро ведет в не пройдённую до этого момента вершину, то алгоритм запускается с нее. В случае если ребер, которые ведут в не рассмотренную вершину, больше нет, то происходит возврат назад.
Реализация на C++
n — количество вершин в графе; adj — список смежности
Остовное дерево
Остованым деревом в связном графе называется любое подмножество ребер, которое является деревом на всех вершинах. То есть любой способ выкинуть несколько ребер так, чтобы осталось дерево на N вершинах и N-1 ребро выделяет в графе остовное дерево.
Обход графа удобно использовать для выделения этого остовного дерева - если выделить каждое ребро, по которому мы прошли в обходе, то получится остовное дерево. Действительно, мы обойдем все вершины, и при этом никогда не пойдем в вершину, в которой уже были, поэтому циклов там не будет. Так что достаточно после прохода по любому ребру добавлять его в ответ.
Практическое задание
7 задача в контесте на выделение остовного дерева в графе.
Breadth-First Search(s)- Поиск в ширину
Алгоритм позволяет найти кратчайший (содержащий наименьшее число ребер) путь из одной вершины графа до всех остальных вершин. В нем сначала посещаются все вершины, смежные с текущей, а затем их потомки.
Kosaraju's Algorithm-Алгоритм Косарайю
Для того чтобы найти компоненты сильной связности, сначала выполняется поиск в глубину, каждый раз выбирается не посещенная вершина с максимальным номером, который был получен при обратном проходе. Полученные деревья являются сильно связными компонентами.
Topological Sort: Топологическая сортировка
Является упорядочиванием вершин бесконтурного ориентированного графа. Его цель состоит в том, чтобы перенумеровать вершины так, чтобы каждое ребро из вершины с меньшим номером вело в вершину с большим. Иными словами, нужно найти перестановку вершин, которая соответствует порядку, задаваемому всеми ребрами графа.
Время работы
Из доказанного следует, что каждая достижимая из \(s\) вершина будет добавлена в очередь ровно \(1\) раз, недостижимые вершины добавлены не будут. Каждое ребро, соединяющее достижимые вершины, будет рассмотрено ровно \(2\) раза. Таким образом, алгоритм работает за \(O(V+ E)\) времени, при условии, что граф хранится в виде списка смежности.
Tarjan's Algorithm-Алгоритм Тарьяна
Этот алгоритм в первую очередь представляет из себя один из вариантов поиска в глубину. Вершины посещаются от корней к листьям, а окончание их обработки происходит на обратном пути.
SCC Algorithms: Компонента сильной связности в орграфе
Максимальные по включению сильно связные подграфы.
Дейкстра на сете
Искать вершину с минимальным \(dist\) можно гораздо быстрее, используя такую структуру данных как очередь с приоритетом. Нам нужно хранить пары \((dist, index)\) и уметь делать такие операции: * Извлечь минимум (чтобы обработать новую вершину) * Удалить вершину по индексу (чтобы уменьшить \(dist\) до какого-то соседа) * Добавить новую вершину (чтобы уменьшить \(dist\) до какого-то соседа)
Для этого используют, например, кучу или сет. Удобно помимо сета хранить сам массив dist, который его дублирует, но хранит элементы по порядку. Тогда, чтобы заменить значение \((dist_1, u)\) на \((dist_2, u)\) , нужно удалить из сета значение \((dist[u], u)\) , сделать \(dist[u] = dist_2;\) и добавить в сет \((dist[u], u)\) .
Данный алгоритм будет работать за \(V O(log V)\) извлечений минимума и \(O(E log V)\) операций уменьшения расстояния до вершины (может быть сделано после каждого ребра). Поэтому алгоритм работает за \(O(E log V)\) .
Заметьте, что этот алгоритм не лучше и не хуже, чем без сета, который работает за \(O(V^2 + E)\) . Ведь если \(E = O(V^2)\) (граф почти полный), то Дейкстра без сета работает быстрее, а если, наример, \(E = O(V)\) , то Дейкстра на сете работает быстрее. Учитывайте это, когда выбираете алгоритм.
2-SAT Checker (2-satisfiability – 2-выполнимость)
Задача 2-SAT состоит в том, чтобы задать переменным значения таким образом, чтобы формула стала истиной. Алгоритм этой задачи состоит из следующих шагов:
1. Строим граф импликаций
2. Затем находим компоненты сильной связности
3. Проверяем, чтобы для каждой переменной х вершины х и !х лежали в разных компонентах. Если это условие не верно, решения не существует.Bipartite Graph Check-Проверка графа на Двудольность
Двудольность графа подразумевает возможность разделения множества вершин графа на две части таким образом, чтобы каждое ребро графа соединяло вершины из этих частей.
Проверка принадлежности вершины кратчайшему пути
Дан ориентированный граф \(G\) , найти все вершины, которые принадлежат хотя бы одному кратчайшему пути из \(s\) в \(t\) .
Запустим из вершины \(s\) в графе \(G\) BFS — найдём расстояния \(d_1\) . Построим транспонированный граф \(G^T\) — граф, в котором каждое ребро заменено на противоположное. Запустим из вершины \(t\) в графе \(G^T\) BFS — найдём расстояния \(d_2\) .
Теперь очевидно, что \(v\) принадлежит хотя бы одному кратчайшему пути из \(s\) в \(t\) тогда и только тогда, когда \(d_1(v) + d_2(v) = d_1(t)\) — это значит, что есть путь из \(s\) в \(v\) длины \(d_1(v)\) , а затем есть путь из \(v\) в \(t\) длины \(d_2(v)\) , и их суммарная длина совпадает с длиной кратчайшего пути из \(s\) в \(t\) .
Раскраска графа в два цвета
Корректной раскраской графа в два цвета назывется такая раскраска, что никакое ребро не соединяет две вершины одного цвета. Графы, которые можно так раскрасить, называют еще двудольными.
С помощью обхода графа легко проверить граф на двудольность и даже вывести цвет каждой вершины - достаточно выделить каждую.
Практическое задание
8 задача в контесте на раскраску графа в два цвета
Cut Vertex & Bridge - Шарнир и Мост
Этот алгоритм используется для нахождения шарниров и мостов в графе.
Шарнир - точка, удаление которой делает граф несвязным.
Мост - ребро, удаление которого увеличивает число компонент связности.Реализация на C++
Рёбра будем хранить как pair<int, int> , где первое число пары — куда оно ведёт; а второе — длина ребра.
Методы систематического обхода вершин графа
Важными задачами теории графов являются задачи глобального анализа как неориентированных, так и ориентированных графов. К этим задачам относятся, например, задачи поиска циклов или контуров, вычисление длин путей между парами вершин, перечисление путей с теми или иными свойствами и т.п. Глобальный анализ графа следует отличать от локального, примером которого может служить задача определения множеств предшественников и преемников фиксированной вершины ориентированного графа.
Базой для решения многих задач глобального анализа являются так называемые алгоритмы обхода или поиска.
Существуют две основные стратегии таких обходов: поиск в глубину и поиск в ширину. Эти стратегии можно описать так.
При условии, что в этом списке существует хотя бы одна неотмеченная вершина, продолжаем "путешествие" из первой такой вершины вершины как возможных продолжений поиска "на потом".
Если же неотмеченных вершин в нет, то возвращаемся из и либо все вершины будут отмеченными, либо окажется, что неотмеченные вершины есть, но из больше никуда пойти нельзя. В последнем случае возможны продолжение поиска из новой вершины или остановка, что определяется конкретной версией алгоритма.
Заметим, что результат поиска в глубину зависит от порядка вершин в списках смежности, представляющих граф, а также от выбора начальной вершины .
На рис. 5.20 показаны примеры поиска в глубину на неориентированном и ориентированном графах.
Рассмотрим неориентированный граф, изображенный на рис. 5.20,а. Списки смежности вершин графа удобно задать кортежами:
Здесь запись означает, что кортеж задает список смежности вершины .
Результаты работы алгоритма с использованием приведенных списков смежности проиллюстрированы графически. При поиске отмечаем вершины, присваивая им номера. При этом каждая новая вершина получает номер, на единицу больший, чем текущая. Вершине присвоим номер 1. Номера остальных вершин, присвоенные им в процессе поиска, приведены на графе. Ребра, по которым из текущей вершины переходим к новой, изображены более толстыми линиями.
Прокомментируем поиск в глубину в ориентированном графе, изображенном на рис. 5.20,б. Пусть списки смежности вершин имеют следующий вид:
"Путешествие" начинается в вершине , и ей присваивается номер 1. Первой в списке смежности вершины стоит вершина . Даем ей номер 2 и продолжаем поиск из этой вершины. В списке смежности последней только одна вершина . Даем ей номер 3 и, так как ее список смежности пуст, возвращаемся в вершину . В списке смежности вершины нет других вершин, кроме вершины , уже помеченной номером 3, поэтому возвращаемся в вершину .
На рис. 5.20,б более толстыми стрелками изображены дуги, по которым из очередной текущей вершины мы переходили к новой.
Именно в обработке сразу всего списка смежности текущей вершины заключается принципиальное отличие поиска в ширину от поиска в глубину: там мы "ныряли" как можно "глубже", а здесь идем с "бреднем", "загребая" сразу все, что можно.
Поиск в ширину заканчивается, когда все вершины полностью обработаны или продолжение поиска невозможно.
Результаты поиска в ширину из вершины в ориентированном графе представлены на рис. 5.21,б.
Обратим внимание на то, что нумерация вершин при поиске в ширину отличается от нумерации вершин при поиске в глубину. Так, в ориентированном графе на рис. 5.21,б мы сразу отмечаем оба элемента списка смежности вершины . Поэтому вершине, получившей при поиске в глубину номер 4, при поиске в ширину присваивается номер 3.
Перейдем теперь к подробному описанию алгоритмов поиска в глубину и поиска в ширину.
Рассмотрим алгоритм поиска в глубину в неориентированном графе. Будем считать, что граф задан списками смежности, собранными в массив лидеров.
При поиске вершины графа нумеруются в порядке их посещения. Номер вершины v графа, присваиваемый ей при поиске в глубину, обозначим и будем называть D-номером.
Итак, фиксируя в графе максимальный остовный лес, мы тем самым фиксируем взаимно однозначное соответствие между множеством обратных ребер и множеством фундаментальных циклов.
Задача
Дан взвешенный ориентированный граф \(G = (V, E)\) , а также вершина \(s\) . Длина ребра \((u, v)\) равна \(w(u, v)\) . Длины всех рёбер неотрицательные.
Найти длину кратчайшего пути от \(s\) до каждой из вершин графа. Длина пути — сумма длин рёбер в нём.Корректность
Утверждение. > 1. Расстояния до тех вершин, которые были добавлены в очередь, посчитаны корректно. > 2. Вершины лежат в очереди в порядке неубывания расстояния, притом разность между кратчайшими расстояними до вершин в очереди не превосходит \(1\) .
Докажем это по индукции по количеству итераций алгоритма (итерация — извлечение вершины из очереди и дальнейшая релаксация).
База очевидна.
Переход. Сначала докажем первую часть. Предположим, что \(dist[v] + 1 < dist[u]\) , но \(dist[v] + 1\) — некорректное расстояние до вершины \(u\) , то есть \(dist[v] + 1 \neq d(u)\) . Тогда по лемме 1: \(d(u) < dist[v] + 1\) . Рассмотрим предпоследнюю вершину \(w\) на кратчайшем пути от \(s\) до \(u\) . Тогда по лемме 2: \(d(w) + 1 = d(u)\) . Следовательно, \(d(w) + 1 < dist[v] + 1\) и \(d(w) < dist[v]\) . Но тогда по предположению индукции \(w\) была извлечена раньше \(v\) , следовательно, при релаксации из неё в очередь должна была быть добавлена вершина \(u\) с уже корректным расстоянием. Противоречие.
Теперь докажем вторую часть. По предположению индукции в очереди лежали некоторые вершины \(u_1, u_2, \dots u_k\) , для которых выполнялось следующее: \(dist[u_1] \leq dist[u_2] \leq \dots \leq dist[u_k]\) и \(dist[u_k] - dist[u_1] \leq 1\) . Мы извлекли вершину \(v = u_1\) и могли добавить в конец очереди какие-то вершины с расстоянием \(dist[v] + 1\) . Если \(k = 1\) , то утверждение очевидно. В противном случае имеем \(dist[u_k] - dist[u_1] \leq 1 \leftrightarrow dist[u_k] - dist[v] \leq 1 \leftrightarrow dist[u_k] \leq dist[v] + 1\) , то есть упорядоченность сохранилась. Осталось показать, что \((dist[v] + 1) - dist[u_2] \leq 1\) , но это равносильно \(dist[v] \leq dist[u_2]\) , что, как мы знаем, верно.Восстановление пути
Пусть теперь заданы 2 вершины \(s\) и \(t\) , и необходимо не только найти длину кратчайшего пути из \(s\) в \(t\) , но и восстановить какой-нибудь из кратчайших путей между ними. Всё ещё можно воспользоваться алгоритмом BFS, но необходимо ещё и поддерживать массив предков \(p\) , в котором для каждой вершины будет храниться предыдущая вершина на кратчайшем пути.
Поддерживать этот массив просто: при релаксации нужно просто запоминать, из какой вершины мы прорелаксировали в данную. Также будем считать, что \(p[s] = -1\) : у стартовой вершины предок — некоторая несуществующая вершина.
Восстановление пути делается с конца. Мы знаем последнюю вершину пути — это \(t\) . Далее, мы сводим задачу к меньшей, переходя к нахождению пути из \(s\) в \(p[t]\) .
Поиск циклов в графе
Циклом в графе \(G\) называется ненулевой путь, ведущий из вершины \(v\) в саму себя. Граф называют ацикличным, если в нем нет циклов.
В обычном dfs мы используем два цвета (1 - вершина посещена, 0 - не посещена), если же нам надо найти цикл, то давайте хранить 3 цвета:
- 0 - вершина не просмотрена
- 1 - мы входили DFS-ом в эту вершину, но еще не вышли (а значит из нее есть путь до текущей),
- 2 - мы входили DFS-ом в эту вершину
Заметим, что цикл будет тогда и только тогда, когда мы пытаемся войти в вершину с цветом 1.
В неориентированном графе также надо дополнительно рассмотреть случай, когда мы идем в предка - это циклом все-таки не считается, для этого нужно отдельно добавить второй аргумент prev, где хранить предыдущую вершину в dfs, и никогда не идти в неё.
Читайте также: