Структуры данных
Графы: Связи между всем
Цели урока
- Понять что такое граф и где применяется
- Выучить терминологию: vertex, edge, degree, path
- Различать типы: directed/undirected, weighted
- Освоить два представления: list и matrix
Предварительные знания
- Хеш-таблицы
Как Facebook знает, что вы знаете друга друга? Как Google Maps находит кратчайший путь? Как npm понимает порядок установки пакетов? Всё это - задачи на графах.
- Google Maps - кратчайший маршрут
- Facebook - люди которых вы можете знать
- npm/pip - разрешение зависимостей
- LinkedIn - степени связи между людьми
Семь мостов Кёнигсберга
В 1736 году Леонард Эйлер задался вопросом: можно ли пройти все семь мостов Кёнигсберга ровно по одному разу и вернуться домой. Он свёл город к абстракции - участки суши стали вершинами, мосты рёбрами, - доказал, что такого пути не существует, и тем самым основал теорию графов. Два стандартных способа хранения, матрица смежности и список смежности, оформились по мере развития области, а книга Фрэнка Харари 'Graph Theory' 1969 года закрепила терминологию вершин, рёбер и степени, которой дисциплина пользуется до сих пор.
Графы повсюду
**Граф** - это набор объектов (вершин) и связей между ними (рёбер).
- **Интернет** - страницы и ссылки
- **Соцсети** - пользователи и дружба
- **Карты** - города и дороги
- **Зависимости** - npm пакеты и imports
- **Биология** - белки и взаимодействия
Что НЕ является графом?
Терминология графов
- **Vertex (вершина)** - узел графа
- **Edge (ребро)** - связь между двумя вершинами
- **Adjacent** - соседние вершины (связаны ребром)
- **Degree** - количество рёбер у вершины
- **Path** - последовательность вершин через рёбра
- **Cycle** - путь, начинающийся и заканчивающийся в одной вершине
Граф: A-B, A-C, A-D, B-C. Какой degree у вершины A?
Типы графов
Directed vs Undirected
Weighted vs Unweighted
Другие типы
- **DAG** - Directed Acyclic Graph (без циклов)
- **Tree** - связный граф без циклов
- **Bipartite** - вершины делятся на 2 группы, рёбра только между группами
Twitter (подписки) - это граф:
Представление: Adjacency List
**Adjacency List** - для каждой вершины храним список соседей.
| Метрика | Adjacency List |
|---|---|
| Память | O(V + E) |
| Проверить ребро | O(degree) |
| Все соседи | O(degree) |
| Добавить ребро | O(1) |
**Лучший выбор** для разреженных графов (мало рёбер относительно вершин).
Adjacency List оптимален для:
Представление: Adjacency Matrix
**Adjacency Matrix** - таблица V×V, где matrix[i][j] = 1 если есть ребро.
| Метрика | Adjacency Matrix |
|---|---|
| Память | O(V²) |
| Проверить ребро | O(1) |
| Все соседи | O(V) |
| Добавить ребро | O(1) |
**Матрица** - для плотных графов или когда нужна быстрая проверка рёбер.
Матрица смежности гарантирует более быстрый обход всех соседей вершины благодаря O(1) проверке ребра.
Чтобы перечислить всех соседей вершины через матрицу, нужно просканировать целую строку O(V). Adjacency list даёт это за O(degree), что в разреженном графе на порядки быстрее.
O(1) проверка одного ребра выглядит как абсолютный выигрыш, и кажется логичным, что 'V проверок по O(1)' лучше списка. Но в разреженном графе degree намного меньше V, и список сразу даёт нужных соседей, не тратя время на 'нулевые' клетки матрицы.
Когда матрица смежности лучше списка?
Представления графов
- Граф = вершины + рёбра
- Directed/Undirected, Weighted/Unweighted
- Adjacency List: O(V+E) память, для разреженных
- Adjacency Matrix: O(V²) память, для плотных
Вопросы для размышления
- Граф - это абстракция отношений. Какие задачи из бизнеса/повседневной жизни часто 'не видят' графовой структуры, хотя она там есть, и как переформулировка задачи в терминах графа меняет подход к её решению?
- Социальная сеть в миллиард пользователей с матрицей смежности невозможна (10^18 ячеек). Какие три-четыре сигнала в задаче должны мгновенно отбрасывать матрицу и оставлять только список или специализированные представления (CSR, edge list)?
- DAG (направленный без циклов) - частный случай графа, на котором становятся возможны топологическая сортировка и быстрая DP. Какие реальные системы (git, build tools, neural nets) опираются именно на это свойство ацикличности?
Следующие темы
Теперь у нас есть граф. Как его обойти? BFS, DFS, топологическая сортировка - в следующем уроке!
- Алгоритмы на графах — BFS, DFS, Dijkstra
Связанные уроки
- ds-14-heaps-intro — Priority queue нужна для обхода графов (Дейкстра)
- ds-17-graph-algorithms — BFS/DFS/Дейкстра строятся поверх структуры графа
- sd-18-consistent-hashing — Consistent hashing - граф на кольце узлов
- net-02-osi-overview — Сеть - граф маршрутизаторов, BGP обходит его
- comp-22-ssa