# конспект · шаг 6 из 6
Конспект: представление графа
Понятия
Граф - множество вершин (V штук) и рёбер (E штук), соединяющих пары вершин. Ребро бывает
ориентированным (в одну сторону) и взвешенным (с числом).
Словарь: степень вершины - число её рёбер; путь - цепочка вершин по рёбрам; цикл - путь,
вернувшийся в начало; связный граф - из любой вершины достижима любая; компонента связности -
максимальный такой кусок; дерево - связный граф без циклов, ровно V − 1 рёбер.
Лемма о рукопожатиях: сумма степеней равна 2E (каждое ребро считается у обоих концов).
Плотность: 0 <= E <= V·(V−1)/2. Разреженный граф - E ≈ V, плотный - E ≈ V². Почти все
большие реальные графы разреженные.
Что унести
| представление | память | соседи вершины | есть ли ребро | когда брать |
|---|---|---|---|---|
| матрица смежности | Θ(V²) |
O(V) |
O(1) |
плотный граф или маленький V |
| списки смежности | Θ(V + E) |
O(deg) |
O(deg) |
разреженный граф, обходы |
| список рёбер | Θ(E) |
нельзя | O(E) |
сортировка по весу, входной формат |
CSR (head + dest) |
Θ(V + E) |
O(deg) |
O(deg) |
большой статический граф |
| неявный (функция) | по посещённым | O(deg) |
- | пространство состояний |
V = 10⁶, E = 10⁷: матрица 125 ГБ против списков 88 МБ
V = 3000, почти полный: матрица 1.1 МБ против списков 36 МБ
Выбор решают два вопроса: какова плотность E / V² и каких операций больше - перебора соседей или
проверок «есть ли ребро». Держать ДВА представления сразу (списки для обхода, множество пар для
проверок) - нормальный приём.
CSR строится за два прохода: степени → префиксные суммы (head) → раскладка соседей (dest).
Соседи вершины v лежат в dest[head[v] : head[v+1]].
Неявный граф - функция соседи(v) вместо хранения; обязательно множество посещённых, иначе обход
зациклится. Так решают пятнашки, кубик, лабиринты, переходы автоматов.
Тихие ошибки: забытая симметрия в неориентированном графе (ребро надо класть обоим концам);
проверка ребра линейным поиском внутри цикла (O(V·E) вместо O(V + E)); матрица на большом
графе; забытое отображение «имя вершины → номер» для строковых данных.
Куда это ведёт
Следующая глава - обход в глубину: на списках смежности он стоит O(V + E), и почти всё
остальное в разделе (топологическая сортировка, компоненты сильной связности, мосты, двудольность)
- надстройки над ним.
Комментарии
Пока нет комментариев. Будь первым!
Оставить комментарий