10 алгоритмов на графах в гифках
Подборка алгоритмов обхода графа с gif-анимациями и объяснениями. Статья поможет ознакомиться и разобраться с различными методами, которые используются в теории графов.
Если хочешь подтянуть свои знания, загляни на наш курс «Алгоритмы и структуры данных», на котором ты:
- углубишься в решение практических задач;
- узнаешь все про сложные алгоритмы, сортировки, сжатие данных и многое другое.
Ты также будешь на связи с преподавателем и другими студентами.
В итоге будешь браться за сложные проекты и повысишь чек за свою работу 🙂
Depth-First Search(s) - Поиск в глубину
Из названия этого метода обхода графа ясно, что в процессе поиска мы идем «вглубь» графа настолько, насколько возможно. Следуя алгоритму, мы последовательно обойдем все вершины графа, которые доступны из начальной вершины. Если ребро ведет в не пройдённую до этого момента вершину, то алгоритм запускается с нее. В случае если ребер, которые ведут в не рассмотренную вершину, больше нет, то происходит возврат назад.
Breadth-First Search(s)- Поиск в ширину
Алгоритм позволяет найти кратчайший (содержащий наименьшее число ребер) путь из одной вершины графа до всех остальных вершин. В нем сначала посещаются все вершины, смежные с текущей, а затем их потомки.
Topological Sort: Топологическая сортировка
Является упорядочиванием вершин бесконтурного ориентированного графа. Его цель состоит в том, чтобы перенумеровать вершины так, чтобы каждое ребро из вершины с меньшим номером вело в вершину с большим. Иными словами, нужно найти перестановку вершин, которая соответствует порядку, задаваемому всеми ребрами графа.
DFS
BFS (Kahn’s algorithm)
Алгоритм основывается на выборе вершин в порядке, подобном топологической сортировке. Сначала находим список начальных вершин, которые не имеют входящих граней, и помещаем их в множество S. В непустом ациклическом графе должна существовать хотя бы одна такая вершина.
После этого количество посещённых вершин увеличивается на 1, а степень всех соседних вершин уменьшается на 1. Если после этого степень соседних вершин обнулится, они помещаются в очередь. Этот шаг будет повторяться, пока очередь не опустеет. Если в итоге количество посещенных вершин не будет равно числу вершин на графе, то сортировка невозможна.
SCC Algorithms: Компонента сильной связности в орграфе
Максимальные по включению сильно связные подграфы.
Kosaraju's Algorithm-Алгоритм Косарайю
Для того чтобы найти компоненты сильной связности, сначала выполняется поиск в глубину, каждый раз выбирается не посещенная вершина с максимальным номером, который был получен при обратном проходе. Полученные деревья являются сильно связными компонентами.
Tarjan's Algorithm-Алгоритм Тарьяна
Этот алгоритм в первую очередь представляет из себя один из вариантов поиска в глубину. Вершины посещаются от корней к листьям, а окончание их обработки происходит на обратном пути.
2-SAT Checker (2-satisfiability – 2-выполнимость)
Задача 2-SAT состоит в том, чтобы задать переменным значения таким образом, чтобы формула стала истиной. Алгоритм этой задачи состоит из следующих шагов:
1. Строим граф импликаций
2. Затем находим компоненты сильной связности
3. Проверяем, чтобы для каждой переменной х вершины х и !х лежали в разных компонентах. Если это условие не верно, решения не существует.
Bipartite Graph Check-Проверка графа на Двудольность
Двудольность графа подразумевает возможность разделения множества вершин графа на две части таким образом, чтобы каждое ребро графа соединяло вершины из этих частей.
BFS
DFS
Cut Vertex & Bridge - Шарнир и Мост
Этот алгоритм используется для нахождения шарниров и мостов в графе.
Шарнир - точка, удаление которой делает граф несвязным.
Мост - ребро, удаление которого увеличивает число компонент связности.
Дополнительные материалы по теме
Сортировки в гифках: 8 самых популярных алгоритмов
Изучаем алгоритмы и структуры данных правильно
Какие алгоритмы нужно знать, чтобы стать хорошим программистом?