Структуры данных
Алгоритмы на графах: BFS, DFS, Dijkstra
Цели урока
- Освоить BFS и DFS
- Найти кратчайший путь (BFS и Dijkstra)
- Реализовать топологическую сортировку
- Понять когда что применять
Предварительные знания
- Основы графов
- Очереди
- Кучи
Google Maps за секунду находит маршрут среди миллионов дорог. npm знает в каком порядке установить 1000 пакетов. Всё это - алгоритмы на графах.
- Google Maps - кратчайший маршрут между городами
- npm/pip - порядок установки зависимостей
- Социальные сети - степени связи между людьми
- Компиляторы - порядок компиляции модулей
BFS, DFS и алгоритмы Тарьяна
Поиск в ширину (BFS) появился у Эдварда Мура в 1959 году как способ найти кратчайший путь в лабиринте, а близкие идеи ещё в 1950-х использовал Эдсгер Дейкстра. Поиск в глубину (DFS) превратился в системный инструмент благодаря Роберту Тарьяну в начале 1970-х: на его основе он в 1972 году дал линейный алгоритм поиска компонент сильной связности (SCC), который до сих пор считается образцовым. Топологическую сортировку, упорядочивание вершин ориентированного ациклического графа, формализовал Артур Кан в 1962 году. Эти классические обходы и есть фундамент, на котором стоят разбираемые в уроке задачи: связные компоненты, порядок зависимостей и анализ достижимости.
BFS: Поиск в ширину
**BFS (Breadth-First Search):** обходим граф по уровням - сначала все соседи, потом соседи соседей.
**BFS находит кратчайший путь** в невзвешенном графе (минимум рёбер)!
BFS использует:
DFS: Поиск в глубину
**DFS (Depth-First Search):** идём вглубь до конца, потом возвращаемся.
| Критерий | BFS | DFS |
|---|---|---|
| Структура | Очередь | Стек/Рекурсия |
| Кратчайший путь | Да (невзвешенный) | Нет |
| Память | O(ширина) | O(глубина) |
| Применение | Shortest path, levels | Cycles, connected |
Для поиска циклов в графе лучше использовать:
Кратчайший путь: BFS vs Dijkstra
Невзвешенный граф: BFS
Взвешенный граф: Dijkstra
**Dijkstra не работает с отрицательными весами!** Для них используйте Bellman-Ford.
Для взвешенного графа без отрицательных весов используем:
Топологическая сортировка
**Топологическая сортировка** - линейный порядок вершин DAG, где для каждого ребра u→v, u идёт перед v.
**Применения:** порядок сборки, расписание задач, разрешение зависимостей в npm/pip.
Топологическая сортировка возможна для:
Когда что использовать
- **BFS:** кратчайший путь (невзвешенный), обход по уровням
- **DFS:** поиск циклов, связность, топ. сортировка
- **Dijkstra:** кратчайший путь (взвешенный, положительные веса)
- **Top Sort:** порядок выполнения задач с зависимостями
Следующие темы
Графы - универсальный инструмент. Следующая структура поможет эффективно работать с динамической связностью.
- Union-Find — Динамическая связность
Связанные уроки
- ds-16-graphs-intro — Представление графа нужно до обхода и поиска путей
- alg-14-dijkstra — Дейкстра - канонический алгоритм кратчайшего пути отсюда
- alg-12-bfs — BFS находит кратчайшие пути в невзвешенных графах
- alg-18-topological — Топологическая сортировка упорядочивает вершины DAG через DFS
- ds-18-union-find — Union-Find отслеживает связность, которую выявляет обход
- net-30-bgp — Маршрутизация в интернете - поиск кратчайшего пути по графу сети
- alg-13-dfs