13. Графы: определения, обходы и кратчайшие пути
Графы — одна из наиболее универсальных структур данных. Они моделируют транспортные сети, социальные связи, зависимости между задачами, структуру интернета и многие другие объекты.
В этом разделе мы изучим:
- Определения и способы хранения — вершины, рёбра, матрица смежности и списки смежности
- Поиск в глубину (DFS) — обход, компоненты связности, дерево DFS, топологическая сортировка, SCC, мосты, точки сочленения, 2-SAT
- Кратчайшие пути — BFS, Дейкстра, A*, Беллман-Форд, Флойд
Определение
Граф $G = (V, E)$ задаётся множеством вершин $V$ и множеством рёбер $E$. В ориентированном графе ребро — упорядоченная пара $(u, v)$; в неориентированном — неупорядоченная $\{u, v\}$.
Свойства
Основные свойства графов:
- $\sum_{v \in V} \deg(v) = 2|E|$ (для неориентированных графов).
- Связный граф с $n$ вершинами содержит не менее $n - 1$ рёбер.
- Дерево — связный граф без циклов — имеет ровно $n - 1$ рёбер.
- Планарный граф: $|E| \leqslant 3|V| - 6$ (теорема Эйлера).
Сводка алгоритмов
| Алгоритм | Задача | Время |
|---|---|---|
| DFS | Обход, компоненты | $O(V + E)$ |
| Топологическая сортировка | Порядок в DAG | $O(V + E)$ |
| Косарайю (SCC) | Сильная связность | $O(V + E)$ |
| Мосты / точки сочленения | Двусвязность | $O(V + E)$ |
| BFS | Кратчайшие пути (невзв.) | $O(V + E)$ |
| Дейкстра | Кратчайшие пути ($w \geqslant 0$) | $O((V+E) \log V)$ |
| Беллман-Форд | Кратчайшие пути (любые $w$) | $O(VE)$ |
| Флойд | Все пары | $O(V^3)$ |
- 13.1. Графы. Определения и способы хранения
- 13.2. Графы. Поиск в глубину
- 13.3. Графы. Алгоритмы поиска кратчайших путей {class=“children children-type-tree children-sort-”}