Поиск в графах — это процесс поиска пути или информации в графе, который состоит из вершин (узлов) и рёбер (связей между узлами).
1. Поиск в ширину (BFS)
Описание: Поиск в ширину (Breadth-First Search, BFS) — это алгоритм, который исследует граф уровнями. Он начинает с заданной вершины и исследует все её соседние вершины, затем переходит к соседям этих вершин, и так далее. BFS использует очередь для хранения временных вершин.
Алгоритмическая сложность: O(V + E), где V — количество вершин, E — количество рёбер в графе.
Применение:
-
Нахождение кратчайшего пути в графах с равными весами рёбер.
-
Поиск компонента связности в неориентированном графе.
-
Применяется в социальных сетях для поиска связей между людьми (например, «рекомендации друзей»).
2. Поиск в глубину (DFS)
Описание: Поиск в глубину (Depth-First Search, DFS) — это алгоритм, который исследует граф, начиная с заданной вершины и двигаясь по одной ветви как можно глубже, прежде чем вернуться и исследовать соседние вершины. DFS использует стек (или рекурсию) для хранения пути.
Алгоритмическая сложность: O(V + E).
Применение:
-
Проверка связности графа.
-
Нахождение компонент связности в графах.
-
Используется для обхода в поиске всех возможных решений, например, в задачах с лабиринтами или головоломками.
3. Алгоритм Дейкстры
Описание: Алгоритм Дейкстры используется для нахождения кратчайшего пути от одной вершины до всех остальных вершин в графе с неотрицательными весами рёбер. Алгоритм работает, начиная с исходной вершины и на каждом шаге выбирает вершину с минимальным расстоянием, обновляя все её соседние вершины.
Алгоритмическая сложность: O(V²) с использованием массива, O((V + E) log V) с использованием очереди с приоритетом.
Применение:
-
Поиск кратчайшего пути в графах, таких как маршруты в транспортных системах.
-
Используется в различных навигационных системах (например, Google Maps).
4. Алгоритм Флойда-Уоршелла
Описание: Алгоритм Флойда-Уоршелла — это алгоритм для нахождения кратчайших путей между всеми парами вершин в графе. В отличие от алгоритма Дейкстры, который решает задачу для одной вершины, Флойд-Уоршелл решает её для всех пар вершин. Алгоритм использует динамическое программирование и подходит для графов с отрицательными весами рёбер (если отсутствуют отрицательные циклы).
Алгоритмическая сложность: O(V³), где V — количество вершин в графе.
Применение:
-
Нахождение кратчайших путей между всеми парами вершин.
-
Используется в графах с отрицательными рёбрами и в задачах с несколькими источниками.