Граф: вершины, рёбра и словарь, без которого дальше никак

Если ты уверенно отличаешь ориентированный граф от неориентированного, знаешь, что такое степень, путь, цикл, связность и дерево как частный случай графа, и помнишь границы E, листай до «Теперь сам».

Как думаешь, что общего у метро, зависимостей пакетов и шахмат

Прежде чем читать дальше, найди общее в трёх задачах. Первая: доехать от одной станции метро до другой с наименьшим числом пересадок. Вторая: установить пакет, у которого есть зависимости, а у тех свои - в каком порядке ставить. Третья: добраться конём с одной клетки шахматной доски на другую за наименьшее число ходов. Задачи из разных миров, но решает их один и тот же код: в каждой есть ОБЪЕКТЫ и ПЕРЕХОДЫ между ними, а вопрос - про достижимость или порядок.

На что это похоже

Карта с городами и дорогами. Города - вершины, дороги - рёбра. Дорога с односторонним движением - ориентированное ребро, обычная - неориентированное. Длина дороги в километрах - вес. Если из города есть кольцевая дорога в него же - это петля. Если два города соединены двумя разными трассами - кратные рёбра. Всё, что дальше будет в разделе, - это вопросы к такой карте: можно ли доехать, за сколько, какой мост разорвёт страну надвое, в каком порядке обходить.

Механизм: словарь, который нужен дальше

вершина (vertex, node)   - объект; их число обозначают V
ребро (edge)             - пара вершин; их число обозначают E
ориентированное ребро    - упорядоченная пара (u → v): из u в v можно, обратно нет
неориентированное        - неупорядоченная пара {u, v}: ходить можно в обе стороны
вес                      - число на ребре (длина, цена, пропускная способность)
петля                    - ребро из вершины в неё же
кратные рёбра            - два и более рёбер между одной парой вершин
простой граф             - без петель и кратных рёбер
мультиграф               - где они разрешены

Вторая половина словаря - про то, что в графе можно найти:

смежные вершины  - соединённые ребром
инцидентность    - отношение «вершина - её ребро»
степень deg(v)   - число рёбер при вершине (в ориентированном: входящая и исходящая
                   степень отдельно)
путь             - последовательность вершин, где соседние соединены ребром
простой путь     - путь без повторяющихся вершин
цикл             - замкнутый путь, НЕ повторяющий рёбер (в простом цикле не
                   повторяются и вершины, кроме совпадающих концов). Без этого
                   условия «сходить к соседу и вернуться» считалось бы циклом,
                   и деревьев не существовало бы вовсе
связный граф     - из любой вершины достижима любая другая (в неориентированном)
компонента связности - максимальный кусок, внутри которого это верно
дерево           - связный граф без циклов; в нём ровно V − 1 рёбер

Заметь: дерево - частный случай графа, а деревья ты уже проходил. Значит обходы, которые ты знаешь по деревьям, - это частный случай обходов графа. Разница будет ровно одна, и о ней следующая глава.

Правило

Граф - пара «множество вершин, множество рёбер»; их количества обозначают V и E (дальше эти буквы всюду означают ЧИСЛА). Ребро соединяет две вершины и бывает ориентированным (в одну сторону) и взвешенным (с числом). Степень вершины - число её рёбер; путь - цепочка вершин по рёбрам; цикл - путь, вернувшийся в начало; связный граф - тот, где из любой вершины достижима любая. Дерево - связный граф без циклов, в нём ровно V − 1 рёбер. Число рёбер лежит между 0 и V·(V−1)/2 для простого неориентированного графа (то есть O(V²)), и от того, ближе оно к V или к V², зависят все дальнейшие решения.

Разбор: сколько рёбер бывает и что значит «плотный»

Посчитаем границы. В простом неориентированном графе каждая пара вершин соединена не больше одного раза, пар всего C(V, 2) = V·(V−1)/2, значит E <= V·(V−1)/2 ≈ V²/2. В ориентированном пар упорядоченных вдвое больше: E <= V·(V−1) ≈ V². Минимум - ноль рёбер (все вершины по отдельности), а чтобы граф был связным, нужно минимум V − 1 ребро (это и есть дерево).

Отсюда два слова, которые дальше будут встречаться постоянно:

разреженный (sparse)  : E растёт как V с точностью до постоянного множителя,
                        то есть E ≪ V² (E = 100·V - всё ещё разреженный)
плотный (dense)       : E ≈ V²        - почти все пары соединены

Примеры из жизни. Дорожная сеть страны: у города редко больше десятка выездов, значит E ≈ 5·V - разреженный. Граф «кто кому звонил» у оператора связи - разреженный. Матрица расстояний между всеми городами (полный граф) - плотный по определению. Социальная сеть - разреженная, хотя отдельные вершины огромной степени там есть.

Почему это важнее, чем кажется: для V = 10⁶ разреженный граф - это порядка 10⁶ рёбер, их можно держать в памяти и обойти за секунды; плотный - 10¹² рёбер, которые не влезут ни в какую память. Алгоритм со сложностью O(V²) на миллионе вершин недопустим, а O(E) - вполне. Поэтому в оценках графовых алгоритмов ВСЕГДА пишут и V, и E отдельно: O(V + E) и O(V²) - это разные миры, хотя на плотном графе они совпадают.

Разбор: одна задача, три разных графа

Возьмём шахматного коня и вопрос «за сколько ходов доберётся с a1 на h8». Что здесь вершина, а что ребро? Вершина - КЛЕТКА (их 64), ребро - возможный ход конём между клетками. Рёбер получается около 168 (у центральных клеток по 8 ходов, у угловых по 2), граф неориентированный (конь ходит в обе стороны) и невзвешенный (каждый ход равноценен). Ответ даст обход в ширину.

Теперь зависимости пакетов: вершина - пакет, ребро A → B означает «A требует B». Граф ОРИЕНТИРОВАННЫЙ, и его правильность - вопрос отсутствия циклов: если A требует B, B требует C, а C требует A, установить нельзя ничего. Порядок установки даст топологическая сортировкаРазбирается в разделе 10, глава «Топологическая сортировка и компоненты сильной связности»: Топологическая сортировка: порядок, в котором можно делать.

И третий: лабиринт из клеток со стенами. Вершина - проходимая клетка, ребро - соседство без стены. Такой граф обычно НЕ хранят: он задан правилом «соседние клетки, если между ними нет стены», и соседей вычисляют на ходу. Это называют неявным графом, и он встречается чаще явных.

Заметь, что в трёх задачах менялось не решение, а МОДЕЛЬ: что назвать вершиной. Половина работы с графами - именно этот выбор, и он не всегда очевиден: в задачах про состояния вершиной бывает целое состояние системы (расстановка фигур, набор включённых ламп, позиция в игре).

Что ломается без этого

Первое: путать вершины и рёбра в оценках. O(V + E) и O(V·E) отличаются катастрофически, а в разговоре «линейный обход графа» означает именно первое. Второе: считать граф связным по умолчанию. Обход из одной вершины найдёт только её компоненту; если в графе несколько компонент, обход надо запускать из каждой непосещённой вершины, иначе половина данных останется необработанной. Третье: забыть про ориентированность. В ориентированном графе достижимость несимметрична: из a в b дойти можно, из b в a - нет; алгоритм, написанный для неориентированного, даст неверный ответ молча. Четвёртое: петли и кратные рёбра. Многие алгоритмы их допускают, но некоторые ломаются (проверка двудольности на петле, формулы степеней), и на реальных данных они появляются неожиданно - из дублей в базе. Пятое: думать, что граф всегда маленький. E растёт квадратично, и представление, годное для тысячи вершин, не годится для миллиона.

Зачем это в работе

Графы - самая универсальная модель в прикладном программировании, и знать их язык нужно уже затем, чтобы УВИДЕТЬ граф в своей задаче. Сборка проекта - граф зависимостей между целями (и make выполняет по нему топологическую сортировку). Пакетные менеджеры, миграции базы, планировщики задач в CI - там же. Маршруты в навигаторе и в логистике - кратчайшие пути. Сети: маршрутизация пакетов, поиск узла, отказ которого разорвёт сеть. Соцсети: рекомендации, поиск сообществ, степени знакомства. Компиляторы: граф потока управления, граф вызовов, распределение регистров через раскраску. Базы данных: планы запросов, блокировки и поиск взаимных блокировок - это поиск цикла. Машинное обучение: вычислительный граф модели. В этом разделе мы разберём, как граф хранить и как его обходить; всё остальное - надстройки над обходом.

Теперь сам

В социальной сети 10 миллионов пользователей, у каждого в среднем 200 друзей. Сколько в графе вершин и рёбер? Разреженный он или плотный? Сколько рёбер было бы в плотном графе такого же размера?