📐 10 алгоритмов для работы с графами, которые должен знать каждый кодер

Знакомимся с десятью маст-хэв для каждого кодера алгоритмами, которые будут полезными для работы с графами (исходный код прилагается).

Зачем вообще изучать графовые алгоритмы?

Графовые алгоритмы представляют собой последовательность шагов для обхода графа через вершины (узлы). Некоторые алгоритмы используются для поиска определенного узла или пути между двумя заданными узлами.

Данные алгоритмы применяют на сайтах социальных сетей, в моделировании конечного автомата, а также во многих других сферах. Я приложил свой исходный код для всех алгоритмов, про которые мы будем говорить ниже.

1. Поиск в ширину (Breadth First Searching)

Поиск в ширину — это рекурсивный алгоритм поиска всех вершин графа или дерева. Обход начинается с корневого узла и затем алгоритм исследует все соседние узлы. Затем выбирается ближайший узел и исследуются все неисследованные узлы. При использовании BFS для обхода любой узел графа можно считать корневым узлом.

Простой алгоритм для BFS, который нужно запомнить:

1. Перейдите на соседнюю нерассмотренную вершину. Отметьте как рассмотренную. Отобразите это. Вставьте ее в очередь.
2. Если смежная вершина не найдена, удалите первую вершину из очереди.
3. Повторяйте шаг 1 и шаг 2, пока очередь не станет пустой.

Схематическое представление обхода BFS:

Ссылка на код: Поиск в ширину

2. Поиск в глубину (Depth First Searching)

Поиск в глубину или обход в глубину — это рекурсивный алгоритм поиска всех вершин графа или древовидной структуры данных.

Алгоритм поиска в глубину (DFS) осуществляет поиск вглубь графа, а также использует стек, чтобы не забыть «получить» следующую вершину для начала поиска, когда на любой итерации возникает тупик.

Простой алгоритм, который нужно запомнить, для DFS:

1. Посетите соседнюю непосещенную вершину. Отметьте как посещенную. Отобразите это. Добавьте в стек.
2. Если смежная вершина не найдена, то вершина берется из стека. Стек выведет все вершины, у которых нет смежных вершин.
3. Повторяйте шаги 1 и 2, пока стек не станет пустым.

Схематическое представление обхода DFS:

Ссылка на код: Поиск в глубину

Если хочешь подтянуть свои знания по алгоритмам, загляни на наш курс «Алгоритмы и структуры данных», на котором ты:

• углубишься в теорию структур данных;
• научишься решать сложные алгоритмические задачи;
• научишься применять алгоритмы и структуры данных при разработке программ.

3. Топологическая сортировка (Topological Sorting)

Топологическая сортировка для ориентированного ациклического графа (DAG) — это линейное упорядочивание вершин, при котором вершина u предшествует v для каждого направленного ребра uv (в порядке очереди). Топологическая сортировка для графа невозможна, если граф не является DAG.

Для одного графа может применяться более одной топологической сортировки.

Простой алгоритм, который следует запомнить, для топологической сортировки:

1. Отметьте u как посещенную

2. Для всех вершин v, смежных с u, выполните:

2.1. Если v не посещенная, то:

2.2. Выполняем TopoSort (не забывая про стек)

2.3. Цикл выполнен

3. Запишите u в стек

Схематическое представление топологической сортировки:

Пример топологической сортировки для этого графа:

5 → 4 → 2 → 3 → 1 → 0

Ссылка на код: Топологическая сортировка

4. Обнаружение цикла с помощью алгоритма Кана (Kahn's Algorithm)

Алгоритм топологической сортировки Кана — это алгоритм обнаружения циклов на базе эффективной топологической сортировки.

Работа алгоритма осуществляется путем нахождения вершины без входящих в нее ребер и удаления всех исходящих ребер из этой вершины.

Ссылка на код: Обнаружение цикла с использованием алгоритма Кана

5. Алгоритм Дейкстры (Dijkstra's Algorithm)

Алгоритм Дейкстры позволяет найти кратчайший путь между любыми двумя вершинами графа. Он отличается от минимального остовного дерева тем, что кратчайшее расстояние между двумя вершинами может не включать все вершины графа.

Ниже проиллюстрирован алгоритм кратчайшего пути с одним источником. Здесь наличие одного источника означает, что мы должны найти кратчайший путь от источника ко всем узлам.

После применения алгоритма Дейкстры:

Ссылка на код: Алгоритм Дейкстры

6. Алгоритм Беллмана-Форда (Bellman Ford's Algorithm)

Алгоритм Беллмана-Форда помогает нам найти кратчайший путь от вершины ко всем другим вершинам взвешенного графа. Он похож на алгоритм Дейкстры, но может обнаруживать графы, в которых ребра могут иметь циклы с отрицательным весом.

Алгоритм Дейкстры (не обнаруживает цикл с отрицательным весом) может дать неверный результат, потому что проход через цикл с отрицательным весом приведет к уменьшению длины пути. Дейкстра не применим для графиков с отрицательными весами, а Беллман-Форд, наоборот, применим для таких графиков. Беллман-Форд также проще, чем Дейкстра и хорошо подходит для систем с распределенными параметрами.

Результат алгоритма Беллмана-Форда:

Ссылка на код: Алгоритм Беллмана Форда

7. Алгоритм Флойда-Уоршалла (Floyd-Warshall Algorithm)

Алгоритм Флойда-Уоршалла — это алгоритм поиска кратчайшего пути между всеми парами вершин во взвешенном графе. Этот алгоритм работает как для ориентированных, так и для неориентированных взвешенных графов. Но это не работает для графов с отрицательными циклами (где сумма ребер в цикле отрицательна). Здесь будет использоваться концепция динамического программирования.

Алгоритм, лежащий в основе алгоритма Флойда-Уоршалла:

D_ij(k) ← min ( D_ij(k-1), D_ij(k-1)+D_kj(k-1))

Ссылка на код: Алгоритм Флойда-Уоршалла

8. Алгоритм Прима (Prim's Algorithm)

Алгоритм Прима — это жадный алгоритм, который используется для поиска минимального остовного дерева из графа. Алгоритм Прима находит подмножество ребер, которое включает каждую вершину графа, так что сумма весов ребер может быть минимизирована.

Простой алгоритм для алгоритма Прима, который следует запомнить:

1. Выберите минимальное остовное дерево со случайно выбранной вершиной.
2. Найдите все ребра, соединяющие дерево с новыми вершинами, найдите минимум и добавьте его в дерево.
3. Продолжайте повторять шаг 2, пока мы не получим минимальное остовное дерево.

Получим:

Ссылка на код: Алгоритм Прима

9. Алгоритм Краскала (Kruskal's Algorithm)

Алгоритм Краскала используется для нахождения минимального остовного дерева для связного взвешенного графа. Основная цель алгоритма — найти подмножество ребер, с помощью которых мы можем обойти каждую вершину графа. Он является жадным алгоритмом, т. к. находит оптимальное решение на каждом этапе вместо поиска глобального оптимума.

Простой алгоритм Краскала, который следует запомнить:

1. Сначала отсортируйте все ребра по весу (от наименьшего к наибольшему).
2. Теперь возьмите ребро с наименьшим весом и добавьте его в остовное дерево. Если добавляемое ребро создает цикл, не берите такое ребро.
3. Продолжайте добавлять ребра, пока не достигнете всех вершин и не будет создано минимальное остовное дерево.

Ссылка на код: Алгоритм Краскала

10. Алгоритм Косараджу (Kosaraju's Algorithm)

Если мы можем достичь каждой вершины компонента из любой другой вершины этого компонента, то он называется сильно связанным компонентом (SCC). Одиночный узел всегда является SCC. Алгоритм Флойда-Уоршалла относится к методам полного перебора. Но для получения наилучшей временной сложности мы можем использовать алгоритм Косараджу.

Простой алгоритм Косараджу, который следует запомнить:

1. Выполните обход графа DFS. Поместите узел в стек перед возвратом.
2. Найдите граф транспонирования, поменяв местами ребра.
3. Извлекайте узлы один за другим из стека и снова в DFS на модифицированном графе.

Получим:

Ссылка на код: Алгоритм Косараджу

В этой статье мы познакомились с самыми важными алгоритмами, которые должен знать каждый программист, работающий с графами. Если хотите подтянуть или освежить знания по алгоритмам и структурам данных, загляни на наш курс «Алгоритмы и структуры данных», который включает в себя:

• живые вебинары 2 раза в неделю;
• 47 видеолекций и 150 практических заданий;
• консультации с преподавателями курса.

Материалы по теме

• 🌳 Деревья и графы: что это такое и почему их обязательно нужно знать каждому программисту
• ❓ Зачем разработчику знать алгоритмы и структуры данных?
  
• ❓ Пройди тест на знание алгоритмов и структур данных
  

Источники

• https://dev.to/rajkousik/the-top-10-algorithms-every-programmer-should-know-in-graph-data-structure-40a5