Подборка алгоритмов обхода графа с gif-анимациями и объяснениями. Статья поможет ознакомиться и разобраться с различными методами, которые используются в теории графов.
Из названия этого метода обхода графа ясно, что в процессе поиска мы идем «вглубь» графа настолько, насколько возможно. Следуя алгоритму, мы последовательно обойдем все вершины графа, которые доступны из начальной вершины. Если ребро ведет в не пройдённую до этого момента вершину, то алгоритм запускается с нее. В случае если ребер, которые ведут в не рассмотренную вершину, больше нет, то происходит возврат назад.
Алгоритм позволяет найти кратчайший (содержащий наименьшее число ребер) путь из одной вершины графа до всех остальных вершин. В нем сначала посещаются все вершины, смежные с текущей, а затем их потомки.
Является упорядочиванием вершин бесконтурного ориентированного графа. Его цель состоит в том, чтобы перенумеровать вершины так, чтобы каждое ребро из вершины с меньшим номером вело в вершину с большим. Иными словами, нужно найти перестановку вершин, которая соответствует порядку, задаваемому всеми ребрами графа.
BFS (Kahn’s algorithm)
Алгоритм основывается на выборе вершин в порядке, подобном топологической сортировке. Сначала находим список начальных вершин, которые не имеют входящих граней, и помещаем их в множество S. В непустом ациклическом графе должна существовать хотя бы одна такая вершина.
После этого количество посещённых вершин увеличивается на 1, а степень всех соседних вершин уменьшается на 1. Если после этого степень соседних вершин обнулится, они помещаются в очередь. Этот шаг будет повторяться, пока очередь не опустеет. Если в итоге количество посещенных вершин не будет равно числу вершин на графе, то сортировка невозможна.
Максимальные по включению сильно связные подграфы.
Kosaraju’s Algorithm-Алгоритм Косарайю
Для того чтобы найти компоненты сильной связности, сначала выполняется поиск в глубину, каждый раз выбирается не посещенная вершина с максимальным номером, который был получен при обратном проходе. Полученные деревья являются сильно связными компонентами.
Tarjan’s Algorithm-Алгоритм Тарьяна
Этот алгоритм в первую очередь представляет из себя один из вариантов поиска в глубину. Вершины посещаются от корней к листьям, а окончание их обработки происходит на обратном пути.
Задача 2-SAT состоит в том, чтобы задать переменным значения таким образом, чтобы формула стала истиной. Алгоритм этой задачи состоит из следующих шагов:
1. Строим граф импликаций
2. Затем находим компоненты сильной связности
3. Проверяем, чтобы для каждой переменной х вершины х и !х лежали в разных компонентах. Если это условие не верно, решения не существует.
Двудольность графа подразумевает возможность разделения множества вершин графа на две части таким образом, чтобы каждое ребро графа соединяло вершины из этих частей.
Этот алгоритм используется для нахождения шарниров и мостов в графе.
Шарнир — точка, удаление которой делает граф несвязным.
Мост — ребро, удаление которого увеличивает число компонент связности.