DATA·II Структуры данных Глава 19 из 65
Шесть рукопожатий
Говорят, любых двух людей на Земле соединяет цепочка из шести знакомств. Это гипотеза, и её можно проверить. Проверим на двух сетях — московском метро и этом самом курсе, — а по дороге выйдем из лабиринта, разольём краску по картинке и выясним, в каком порядке читать главы.
Структуры данных
- 13 Сложность
- 14 Массивы
- 15 Стек и очередь
- 16 Хеш-таблицы
- 17 Деревья
- 18 Кучи
- 19 Графы вы здесь
Опирается на: 15 · Стек, очередь и калькулятор 08 · Словарь и телеграф
Что вы унесёте из главы
- хранить граф словарём списков и находить в нём путь с наименьшим числом рёбер обходом в ширину
- обходить граф в глубину — рекурсией и своим стеком — и пользоваться этим для лабиринтов, заливки и подсчёта кусков сети
- упорядочивать задачи с зависимостями топологической сортировкой и замечать круг, из-за которого порядка нет
В конце прошлой главы данные перестали жить поодиночке. Друзья знакомы с друзьями друзей, станции метро соединены перегонами и переходами, главы этого учебника ссылаются на главы, которые надо прочесть раньше. О таких данных первым делом спрашивают, как отсюда дойти туда и за сколько шагов. Есть старая гипотеза: любых двух людей на Земле соединяет цепочка не длиннее шести рукопожатий. Звучит как тост, но её можно проверить. Проверять будем обходом графа, который соберём сами, на двух наборах данных: московском метро и самом этом курсе.
Письма из Небраски
Через сорок с лишним лет опыт повторили без писем. В 2011 году исследователи из Facebook и Миланского университета — Ларс Бакстром, Паоло Больди, Марко Роза, Йохан Угандер и Себастьяно Винья — взяли граф дружбы всех активных пользователей: около 721 миллиона человек и 69 миллиардов дружб. Среднее расстояние между двумя людьми вышло 4,74 шага, то есть 3,74 промежуточных знакомых. Статья 2012 года называлась «Четыре степени разделения».
Два опыта мерили разное. У Милгрэма каждый участник видел только своих знакомых и передавал письмо наугад, по чутью, так что дошедшая цепочка могла быть далеко не самой короткой. Исследователи Facebook видели всю сеть сразу и считали кратчайшие цепочки. Для этого нужен способ быстро находить самую короткую цепочку между двумя точками сети: пар людей там четверть квинтиллиона.
Прибор: граф
Сеть знакомств, метро, лабиринт, ссылки между страницами — всё это одна структура. Есть объекты и есть связи между парами объектов. Объекты называют вершинами, связи — рёбрами, а всё вместе — графом. Граф помнит только, что с чем связано. Ни положения станций на карте, ни длины перегонов в нём нет, пока мы сами их не допишем.
Первым так посмотрел на задачу Леонард Эйлер в 1735 году, когда доказал, что по семи мостам Кёнигсберга нельзя пройти, побывав на каждом ровно один раз: острова и берега стали вершинами, мосты — рёбрами. Эта история и её математика разобраны в «Царице наук», в главе «Семь мостов». Теоремы пусть остаются там, а нам нужны программы, которые по графам ходят.
Рёбра бывают двух видов. Дружба взаимна, по перегону метро ездят туда и обратно: такое ребро идёт в обе стороны. А «главу 17 надо прочесть перед главой 18» — уже стрелка, от 17 к 18. Граф со стрелками называют ориентированным. Число рёбер у вершины называют её степенью: у конечной станции степень 1, у пересадочного узла — пять или шесть.
В песочнице курса лежит граф московского метро, собранный из открытого справочника станций: 17 линий, как их перечисляет справочник, считая МЦК и Большую кольцевую, без МЦД. Каждая станция каждой линии в нём — отдельная вершина. Рёбра — перегоны между соседними станциями одной линии и переходы между линиями: «Киевская» кольцевой и «Киевская» Филёвской — две вершины, и между ними ребро-пересадка. Переходы мы восстановили по координатам: станции разных линий ближе 450 метров друг от друга считаем связанными. Почти всегда это настоящие пересадки, но кое-где — прогулка по улице. Посмотрим на сырые данные и сложим их в граф.
Номер перед двоеточием — линия: 5 — кольцевая, 3 — Арбатско-Покровская, 4 — Филёвская. Название с номером линии получается уникальным, и им удобно называть вершину. Сам граф — словарь из главы 8: ключ — вершина, значение — список её соседей. Такой способ хранить граф называют списками смежности. Ребро без направления записано дважды, в оба списка, поэтому сумма длин всех списков — 808, вдвое больше числа рёбер.
Дальше в главе граф метро будет загружать одна строка: graph, names = load_metro() из модуля курса cs.graphs. Она делает то же, что ячейка выше, и ещё отдаёт словарь названий без номера линии. Порядок станций на линиях в файле восстанавливали по координатам, и на развилке Филёвской линии, на конце Люблинско-Дмитровской и у «Шелепихи» он вышел неверным; эти пять перегонов в файле поправлены вручную.
Таблица вместо списков
Есть и другой способ хранить граф — таблица $n \times n$, где на пересечении строки $a$ и столбца $b$ стоит 1, если ребро между $a$ и $b$ есть, и 0, если нет. Её называют матрицей смежности. Проверка «есть ли ребро» в ней стоит одно обращение к клетке, $O(1)$, а в списках смежности надо пройти по списку соседей. Но за это платят памятью: клеток $n^2$, сколько бы ни было рёбер.
Граф дружбы Facebook из исследования 2011 года: 721 миллион вершин, 69 миллиардов рёбер. Сколько места заняла бы его матрица смежности, если тратить на клетку всего один бит?
Клеток $721 \cdot 10^6$ в квадрате, около $5{,}2 \cdot 10^{17}$. В байте восемь бит, выходит $6{,}5 \cdot 10^{16}$ байт — 65 петабайт, и почти все клетки — нули: у человека в среднем около двухсот друзей, а не 721 миллион. Списки смежности хранят только сами дружбы: $2 \cdot 69 \cdot 10^9$ записей, по 4 байта на номер — около 550 гигабайт, в сто с лишним раз меньше. Матрица хороша для маленьких или плотных графов, где связаны почти все со всеми. Сети из жизни почти всегда редкие, и для них берут списки.
В метро то же самое: матрица из $312 \times 312 = 97\,344$ клеток, из них единиц 808 — меньше процента. Дальше в главе все графы — словари списков.
Волна
Представим, что Милгрэм разрешил пересылать письмо не одному знакомому, а всем сразу. В первый день письмо получают знакомые отправителя. Во второй — их знакомые, кроме тех, у кого оно уже есть. В третий — следующий круг. Письмо расходится волной, как круги по воде, и день, в который оно впервые пришло к человеку, — это длина самой короткой цепочки до него. Кто получил письмо повторно, выбрасывает его: короче цепочка от этого не станет.
Программе остаётся решить, кого обрабатывать следующим. Ответ подсказывает сама волна: того, кто получил письмо раньше. Первым пришёл — первым обслужен; это очередь из главы 15, deque с append в хвост и popleft из головы. Так устроен обход в ширину, по-английски breadth-first search, BFS. В главе 17 он уже обходил дерево по этажам. Отличие одно: в дереве к каждому узлу ведёт единственный путь, а в графе — много, поэтому надо помнить, кто уже получил письмо. Пусть волна пойдёт от «Сокольников», откуда в 1935 году начиналась первая линия метро.
Словарь dist работает за двоих: хранит ответ и помнит, кто уже получил письмо. Каждая строка вывода — круг волны: на расстоянии 1 три станции («Красносельская», «Преображенская площадь» и переход на Большую кольцевую), на расстоянии 8 — тридцать одна, самый широкий круг. Последний, двадцать четвёртый, — одна «Бунинская аллея» на юго-западе. Волна дошла до всех 312 станций.
Поиграйте с волной. От станций кольцевой линии она обходит город быстрее, чем от конечных: из центра до любой окраины ближе, чем с окраины до противоположной. А рядом с МЦК и Большой кольцевой видно, как кольца подхватывают волну и разносят её по кругу.
Дорога задом наперёд
Расстояние — полдела, хочется знать саму дорогу. Для этого каждая вершина запоминает, от кого к ней впервые пришло письмо. Эти записи образуют дерево с корнем в начальной вершине, а путь до цели читается по ним задом наперёд: от цели к тому, кто её нашёл, от него к его родителю — и так до старта. Остаётся перевернуть список.
Двадцать рёбер: семь перегонов по оранжевой линии, переход на кольцевую, пять перегонов по кольцу, переход на красную и ещё шесть перегонов на юго-запад. Число рёбер на самом коротком пути называют расстоянием между вершинами, а сам путь — кратчайшим путём. Но почему путь, найденный волной, самый короткий? Обход ведь не перебирает все пути.
Если вершина $u$ достижима из $s$, обход в ширину присваивает ей dist[u], равное наименьшему числу рёбер на пути из $s$ в $u$.
Сначала заметим порядок в очереди. Вершины попадают в неё с метками $d + 1$, где $d$ — метка вершины, которую сейчас обрабатывают. Поэтому в любой момент метки в очереди идут по неубыванию и различаются не больше чем на единицу: в голове несколько вершин с меткой $d$, в хвосте — с $d + 1$. Значит, вершины обрабатываются по неубыванию меток.
Теперь индукция по расстоянию $k$. При $k = 0$ это одна вершина $s$, её метка 0. Пусть все вершины на расстоянии не больше $k$ получили верные метки. Возьмём $u$ на расстоянии $k + 1$, и пусть $w$ — предпоследняя вершина кратчайшего пути до неё; $w$ на расстоянии $k$, и её метка $k$. Метку меньше $k + 1$ вершина $u$ получить не может: по предположению индукции такая метка означала бы расстояние меньше $k + 1$. А больше $k + 1$ — тоже: метки $k + 2$ и больше раздают вершины с метками от $k + 1$, а их обрабатывают после $w$. Когда же обработают $w$, вершина $u$, если её ещё не нашли, получит метку $k + 1$.
Сколько стоит обход? Каждая вершина входит в очередь один раз, потому что второй раз её не пустит проверка if u not in dist. Каждый список соседей просматривается один раз — когда его вершину достают из очереди. Всего $O(V + E)$, где $V$ — число вершин, $E$ — рёбер, то есть линейное время из главы 13. Для метро это тысяча с небольшим шагов. Но не забудьте deque: с обычным списком и pop(0) каждое извлечение сдвигает всю очередь, как в главе 14, и на большом графе обход станет квадратичным.
Проверка гипотезы: метро
Прибор готов. Гипотеза «любые двое — в шести рукопожатиях» для метро звучит так: от любой станции до любой не больше шести рёбер. Проверять будем в лоб: пустить волну из каждой станции по очереди и собрать все расстояния. Сначала сделайте ставку.
Каково среднее расстояние между двумя станциями московского метро — сколько в среднем перегонов и переходов на самом коротком пути?
Около 11 — почти втрое меньше, чем у самой далёкой пары. Проверьте ячейкой ниже.
Триста двенадцать волн и сорок восемь с половиной тысяч пар сервер перебирает за долю секунды. Гипотеза для метро не подтвердилась: в среднем между станциями 11,3 ребра, а пар, между которыми не больше шести рёбер, меньше пятой части. Самые далёкие друг от друга — «Физтех» на севере и «Бунинская аллея» на юго-западе: 32 ребра. Наибольшее расстояние в графе называют его диаметром.
Почему у Facebook вышло меньше пяти, а у метро — больше одиннадцати? Вспомним рассуждение героя Каринти. Если у каждого $k$ знакомых и круги не повторяются, то за $d$ шагов дотягиваешься примерно до $k^d$ человек. Чтобы охватить всех $n$, нужно $k^d \approx n$, то есть $d \approx \ln n / \ln k$. Для Facebook $n \approx 7{,}2 \cdot 10^8$, а знакомых в среднем $k \approx 190$, и оценка даёт $d \approx 3{,}9$ — недалеко от измеренных 4,74. У метро в среднем $k \approx 2{,}6$ соседа на станцию, и оценка обещает около шести. На деле выходит вдвое больше.
Оценка ошибается, потому что в метро круги повторяются. Сосед моего соседа на линии — снова станция той же линии, и волна вдоль линии растёт не умножением, а прибавлением: по станции на шаг. В ячейке волна.py круги растут медленно — 1, 3, 4, 9, 13, 19, — а потом сжимаются. В сети знакомств почти так же: большинство ваших друзей живут рядом, учились или работают с вами и знакомы друг с другом. Но у кого-то есть двоюродный брат во Владивостоке, у кого-то однокурсник в Берлине. Таких дальних связей немного, но тесным мир делают как раз они.
Так в 1998 году объяснили «тесный мир» Дункан Уоттс и Стивен Строгац в статье в журнале Nature. Они взяли граф-кольцо, где каждый связан только с ближайшими соседями, и стали перекидывать немногие рёбра на случайные дальние вершины. Местный уют почти не менялся — друзья ваших друзей оставались вашими друзьями, — а среднее расстояние падало обвалом уже от нескольких процентов перекинутых рёбер. Проверим это на метро: пророем между случайными станциями туннели.
Двадцать туннелей, пять процентов к четырёмстам рёбрам метро, снижают среднее расстояние с 11,3 до 8,8. Сто туннелей — вдвое, до 5,7: метро становится «тесным миром». Триста — до четырёх, почти как у Facebook. В большом графе эффект ещё сильнее: чем больше вершин, тем длиннее обходные пути, которые срезает каждый туннель.
А этот курс?
Второй граф нашего исследования — сам учебник. Его 66 глав — вершины, а стрелка ведёт от главы к той, что на неё опирается: «рекурсия → деревья» значит, что рекурсию читают раньше. Модуль курса отдаёт эти связи одной строкой load_course() — словарём «глава → главы, которые нужно прочесть до неё». Для «рукопожатий» направление пока забудем: пусть глава и её предшественница будут знакомыми, без старшинства.
Курс оказался тесным миром: в среднем 3,4 шага между главами, и только у девяти пар из 2145 расстояние больше шести, хотя связей у главы в среднем меньше четырёх. Оценка Каринти даёт $\ln 66 / \ln 3{,}7 \approx 3{,}2$ — почти точно. В отличие от метро, курс не привязан к плоскости. Рекурсия, словари, деревья, сложность — его «общительные люди»: у каждой из этих глав по восемь-девять связей с самыми разными частями курса, от сортировок до игровых ботов. Через них любая глава в нескольких шагах от любой.
Мир тесен, когда круги волны растут умножением: у знакомых ваших знакомых появляются новые люди. Для этого хватает немногих дальних связей. Если же связи только местные, как у станций метро, круги растут прибавлением, и расстояния выходят большими.
Нить Ариадны
У волны есть странность, которую легко не заметить: вершины, которые она обрабатывает подряд, на карте могут быть на разных концах города — станция на севере, потом на юге, потом снова на севере. Программе всё равно, она видит весь граф сразу. Человеку в лабиринте не всё равно: перескочить с одного края волны на другой он не может. Ему остаётся идти вперёд или возвращаться туда, откуда пришёл.
Как выйти из лабиринта, знали ещё в мифах: Ариадна дала Тесею клубок, и нить, которую он разматывал за собой, вывела его обратно от Минотавра. Нить отмечает путь от входа до места, где вы стоите. Пошли вперёд — нить удлинилась. Упёрлись в тупик — сматываете нить до последней развилки и пробуете другой коридор. Так устроен обход в глубину, depth-first search, DFS. Нить — это стек: последний пройденный коридор сматывается первым. А готовый стек у нас уже есть — стек вызовов из главы 9: рекурсивный вызов — шаг вперёд, возврат из вызова — шаг назад.
Правила Тремо — тот же обход в глубину, записанный мелом на стенах: чёрточки заменяют множество посещённых, а «уходить по коридору, по которому впервые пришли» — сматывать нить. Вот обход в глубину на графе метро. Список thread — нить: в него дописывают станцию, когда в неё входят, и вычёркивают, когда из неё возвращаются ни с чем.
Дорога нашлась, но какая: 199 рёбер вместо двадцати, и по пути обход заглянул на 245 станций из 312. Он проехал оранжевую линию насквозь, через центр до самого юга, перебрался на Бутовскую, по серой линии вернулся на север, проехал почти полный круг по МЦК — и так побывал на двенадцати линиях, прежде чем случайно вышел к цели. Обход в глубину находит какой-нибудь путь: он упрямо идёт вперёд и о длине не думает. Зато ему не нужно перескакивать: каждый его следующий шаг — сосед текущего или возврат на шаг назад. Поэтому его можно пройти ногами, а волну — нельзя.
Лабиринт — тоже граф: клетки — вершины, рёбра соединяют соседние свободные клетки. Списки соседей хранить не обязательно, их легко вычислить: у клетки $(r, c)$ соседи $(r \pm 1, c)$ и $(r, c \pm 1)$, если там не стена. Следующая ячейка лабиринт роет и проходит. Роет обход в глубину: из комнаты — в случайную нетронутую соседнюю, ломая стену, а из тупика — назад по стеку. Выход ищет волна.
Лабиринт, вырытый обходом в глубину, — дерево: в каждую комнату стену ломали один раз, поэтому путь между любыми двумя клетками единственный. Тогда и волна, и нить найдут одну и ту же дорогу, а разница будет лишь в том, сколько клеток они осмотрят по пути. Запустите гонку и поменяйте лабиринт.
В лабиринте-дереве нить приходит первой примерно в двух случаях из трёх: она бежит по одному коридору и на соседние шагов не тратит, тогда как волне приходится расширяться во все стороны сразу. Но стоит пробить в стенах петли, как путь нити становится в среднем почти вдвое длиннее кратчайшего, а бывает и вчетверо. В чистом поле её путь — змейка, в среднем вчетверо длиннее кратчайшей дороги к выходу. Скорость при выборе между ними почти ни при чём: оба обхода в худшем случае осматривают всё, за $O(V + E)$. Нужен кратчайший путь — берите волну. Если же надо обойти всё, пройти лабиринт ногами или проверить, есть ли путь вообще, хватит и нити.
Ведро с краской
В любом графическом редакторе есть ведро: касаетесь пикселя — и вся область того же цвета вокруг него перекрашивается, а за контуром краска не течёт. Это тоже обход графа. Вершины — пиксели, ребро соединяет два соседних пикселя одного цвета, и ведро красит всё, до чего можно дойти от пикселя под пальцем. Как в лабиринте, граф нигде не записан: соседей вычисляют по координатам. Пиксель перекрашивают в момент, когда нашли, — так новый цвет заодно служит отметкой «уже был здесь», и отдельное множество не нужно.
Протащите ползунок. Краска, вылитая в угол, расходится ромбом: так на клетчатой бумаге выглядят круги волны. Она обтекает фигуры и затекает в квадрат через дырку внизу, а круг замкнут, и внутри него остаётся белое. Строчка if old == paint стоит не зря: без неё ведро той же краски крутилось бы вечно, потому что каждый перекрашенный пиксель снова оказывался бы «старого» цвета.
Со стеком вместо очереди ведро красит ту же область в другом порядке: длинными полосами, которые упираются в стенку и разворачиваются. А вот переключатель «8 соседей» меняет результат: если соседями считать и пиксели по диагонали, краска просачивается через тонкую косую линию, ведь две клетки, касающиеся углами, для неё теперь связаны. Поэтому редакторы почти всегда льют краску по четырём соседям.
Заливку соблазнительно написать рекурсией: покрасить пиксель и вызвать себя для четырёх соседей. Это четыре строчки, и на маленьких картинках они работают. Но рекурсия идёт в глубину, и на однотонной картинке она проползает змейкой через все пиксели, не возвращаясь, — глубина вызовов становится равной площади.
Квадрат 40 на 40 — всего 1600 пикселей, — и рекурсия уже упирается в предел глубины из главы 9. Фотография в двенадцать мегапикселей ей недоступна в принципе. Лекарство мы знаем из главы 15: стопку недоделанных дел держать в обычном списке, который может быть сколь угодно длинным. Поэтому на больших графах обход в глубину пишут своим стеком, а рекурсию оставляют для графов, о которых точно известно, что они неглубокие.
Ведро прячется во многих местах. «Волшебная палочка» в фоторедакторе выделяет связную область похожего цвета. В «Сапёре» щелчок по пустой клетке открывает всю пустую область вокруг. В го группу камней, касающихся сторонами, снимают с доски, когда вокруг неё не осталось свободных пунктов, и программа находит группу той же заливкой.
Сколько кусков
Заливка отвечает на вопрос «что связано с этим пикселем». Если лить ведро снова и снова, каждый раз в ещё не закрашенное место, картинка распадётся на куски, внутри которых всё связано, а между ними — нет. Такие куски называют компонентами связности. Найти их можно любым обходом: запускаем его из первой вершины, которую ещё никто не видел, и всё, до чего он дотянулся, — одна компонента.
Подсчёт компонент — первое, что стоит сделать с новыми данными о сети. Мы ожидаем, что метро связно, а без переходов распадается ровно на линии. Если кусков окажется больше, значит, в данных дыра: пропущен перегон или станция записана под двумя именами.
Метро — один кусок, а без переходов — семнадцать, по числу линий в данных, и в каждом куске станции одной линии. Эту проверку данные прошли. Самые большие куски — два кольца, МЦК и Большая кольцевая, по 31 станции, а самый маленький — Каховская линия из трёх станций. На ней видно, чего подсчёт кусков не ловит. С 2023 года Каховской линии нет: её станции вошли в Большую кольцевую. Справочник же держит их ещё и отдельной линией, так что у нас эти три станции записаны дважды и копии соединены пересадками. Проверка дубля не заметила: кусок честно совпал с линией, которую называет справочник. На расстояния он почти не влияет: без него среднее и самая далёкая пара остаются прежними. Та же функция считает острова на карте, группы людей в соцсети, между которыми нет ни одной дружбы, и отдельные цепи в электрической схеме. Острова ждут вас в задачах.
В каком порядке читать
До сих пор мы забывали, куда смотрят стрелки. Вернём им направление. Стрелка «рекурсия → деревья» значит: прежде чем читать про деревья, прочтите про рекурсию. Расстояния здесь мало кого волнуют. Читателю нужен порядок: выстроить все главы в ряд так, чтобы каждая шла после всех, на которые она опирается. Такой порядок называют топологической сортировкой.
Такой порядок есть не всегда. Если глава А требует главы Б, Б требует В, а В требует А, начать нельзя ни с одной: стрелки замкнулись в круг. Путь по стрелкам, который возвращается в начальную вершину, называют циклом, а ориентированный граф без циклов — ориентированным ациклическим, по-английски DAG. Граф глав курса должен быть таким, иначе мы где-то ошиблись в плане.
Идея Кана: читать то, что уже можно. У каждой главы заведём счётчик — сколько нужных ей глав ещё не прочитано. Главы со счётчиком ноль готовы, они ждут в очереди. Берём готовую, читаем, и у всех глав, которые её ждали, счётчик уменьшается на единицу. Чей счётчик дошёл до нуля — встаёт в очередь готовых. Если в конце прочитаны не все главы, значит, оставшиеся ждут друг друга по кругу.
Порядок Кана начинается так же, как наш: 0, 1, 2, 3. А потом — 28: глава «Всё есть биты» о двоичных числах опирается только на вторую, «Имена и значения», и стала готова одновременно с третьей. Эта глава о графах в порядке Кана стоит на 39-м месте из 66. Нумерация курса — тоже правильный порядок, один из очень многих: у графа, где много глав независимы друг от друга, топологических сортировок астрономически много. Последняя строка показывает, что будет, если вступление потребует графов: глава 0 ждёт главу 19, та через цепочку ждёт главу 0, и Кан сдаётся: очередь готовых пустеет раньше времени.
Почему Кан всегда находит порядок, если циклов нет? Пусть он остановился, а непрочитанные главы остались. У каждой из них счётчик не ноль, значит, у каждой есть непрочитанная предшественница. Встанем на любую из оставшихся и пойдём к её непрочитанной предшественнице, от неё — к следующей. Идти можно бесконечно, а глав конечное число, поэтому рано или поздно мы вернёмся туда, где уже были, и получится цикл. Значит, без циклов Кан не останавливается, пока не прочтёт всё. Каждая стрелка при этом уменьшает счётчик один раз, и время снова $O(V + E)$.
Порядок умеет строить и обход в глубину: идти по стрелкам к предшественницам и записывать главу, когда с ними покончено, — как обратный обход из главы 17, где узел идёт после своих веток. А чтобы узнать, что нужно прочесть до одной главы, хватит одного обхода по стрелкам назад от неё.
Чтобы читать о шифровании с открытым ключом в главе 60, не нужно читать 59 глав подряд: хватит шестнадцати. Для этой главы — пятнадцати, и в списке нет ни деревьев, ни куч: графы стоят на списках, словарях, рекурсии и очереди.
Готовое: graphlib и pip
С Python 3.9 топологическая сортировка есть в стандартной библиотеке — модуль graphlib. Он ждёт граф в том же виде, что у нас, «вершина → те, кто раньше», и при цикле не возвращает None, а бросает исключение CycleError с самим кругом внутри.
Круг читается так: деревья нужны рекурсии, рекурсия — сложности, сложность — деревьям. Ту же задачу решает pip: у matplotlib свои зависимости, у тех свои, и с версии 6.1 (2015) pip ставит их в топологическом порядке, зависимости раньше зависящих: иначе пакет, которому уже при установке нужна его зависимость, мог её не найти. Так же make решает, что пересобрать первым, а электронная таблица — какую ячейку пересчитать после правки: формула ждёт ячеек, на которые ссылается. Сообщение о циклической ссылке в таблице — тот же случай, что у Кана с непрочитанными главами.
Задачи
Пять задач на пять приёмов главы: волна с обратной дорогой, заливка, поиск круга, порядок с правилом выбора и центр сети. Во всех, кроме островов, граф — словарь списков, как в главе. Тесты проверяют края — пустые графы, недостижимые цели, вершины без рёбер — и большие входы, на которых рекурсия и pop(0) не успевают.
Напишите shortest_path(graph, start, goal): список вершин пути от start до goal с наименьшим числом рёбер, или None, если до цели не дойти. Если start == goal, путь — [start]. Граф — словарь «вершина → список соседей»; рёбра могут быть и стрелками, тогда идти можно только по направлению стрелки. Кратчайших путей бывает несколько — подойдёт любой. В тестах есть граф из 300 000 вершин, на него даётся две секунды. Заготовка находит дорогу всегда, но не всегда самую короткую.
Список с append и pop() — это стек: последним пришёл, первым ушёл. Обход получился в глубину. Попробуйте граф {0: [1, 2], 1: [3], 2: [4], 4: [5], 5: [3], 3: []}: какой путь до 3 выдаст заготовка?
Нужна очередь. queue.pop(0) даст верный ответ, но на графе в сотни тысяч вершин каждое извлечение будет сдвигать весь список. Возьмите deque и popleft.
Одна замена — очередь вместо стека — и обход идёт кругами, а первая найденная дорога к вершине становится кратчайшей, как доказано в разделе «Волна». graph.get(v, []) не падает на вершинах, у которых нет своего ключа: в графе со стрелками так бывает с вершинами, из которых ничего не выходит. Проверка v == goal останавливает обход, как только цель достали из очереди, — дальше искать незачем.
Карта — список строк одинаковой длины (или списков символов): # — суша, . — вода. Остров — кусок суши, связный по сторонам клеток; клетки, касающиеся только углами, — разные острова. Напишите count_islands(grid) — сколько на карте островов. Карту менять нельзя. На такой карте их шесть:
##....# ##...## ...#... ....... #.#.###
В тестах есть карты 500 × 500, на каждую даётся четыре секунды. Заготовка верно считает острова на маленьких картах. Найдите карту, на которой она падает, и исправьте.
Каждый новый остров — одна заливка из первой встреченной клетки суши. Это верно. Беда в том, как заливка написана: рекурсия. Какой глубины будет стек вызовов на острове-змейке через всю карту 500 × 500?
Перепишите flood со своим стеком, как в ячейке глубина.py: клетку отмечаем в seen, когда кладём в стек, а в цикле снимаем клетку со стека и кладём её непросмотренных соседей-сушу.
Острова — это компоненты связности графа клеток-суши, и счёт идёт так же, как в ячейке куски.py: обход из каждой ещё не виденной клетки находит целый остров. Своя стопка может вырасти до размера карты, и ничего страшного: это обычный список. Карта не меняется, потому что отметки живут в отдельном множестве seen, а не в самой карте. Время — $O(\text{клеток})$: каждую клетку кладут в стек не больше одного раза.
Напишите has_cycle(graph): есть ли в ориентированном графе цикл — путь по стрелкам, который возвращается в свою начальную вершину. Граф — словарь «вершина → список вершин, куда ведут стрелки»; вершина может встречаться только внутри списков, без своего ключа. Петля {1: [1]} — тоже цикл. В тестах есть цепочки в сто тысяч вершин, на ответ — две-три секунды.
Заготовка обходит граф в глубину и кричит «круг», как только приходит в вершину, где уже была. Она ошибается даже на четырёх вершинах.
Возьмите ромб {'A': ['B', 'C'], 'B': ['D'], 'C': ['D'], 'D': []}. В D можно прийти двумя дорогами, но круга нет: из D в A не вернуться. В графе без направлений повторная встреча и правда означала бы цикл, а со стрелками — нет.
Первый способ — алгоритм Кана из раздела «В каком порядке читать»: если упорядочить удаётся не все вершины, круг есть. Не забудьте вершины, которые встречаются только в списках, и считайте, сколько стрелок входит в каждую.
Второй способ — обход в глубину с тремя состояниями вершины: ещё не видели, сейчас на нити (обход внутри неё) и закончили. Круг — это стрелка в вершину, которая сейчас на нити. Пишите его своим стеком: цепочка в сто тысяч вершин рекурсии не по силам.
Счётчик здесь — сколько стрелок входит в вершину, то есть сколько у неё «предшественниц». Кан снимает вершины, в которые больше никто не ведёт, и если готовые кончились раньше вершин, то оставшиеся ждут друг друга по кругу — это доказано в разделе про порядок чтения. Ромб Кан проходит спокойно: D снимается последней, когда обе дороги к ней пройдены. Рекурсии нет, поэтому длинные цепочки не страшны. Время — $O(V + E)$.
Главы пронумерованы целыми числами. Словарь prereq говорит, какие главы надо прочесть раньше: {4: [2, 3]} значит, что перед главой 4 нужно прочесть 2 и 3. Напишите reading_order(prereq) — порядок чтения всех глав, где каждая стоит после своих предшественниц. Главы, которые встречаются только в списках, тоже читают. Правило выбора: из всех глав, которые уже можно читать, всегда берите главу с наименьшим номером, — тогда ответ единственный. Если порядка нет, верните None. В тестах есть план из 80 000 глав, на него даётся три секунды.
Например, для {5: [], 4: [], 1: [5]} ответ [4, 5, 1]: сначала готовы 4 и 5, берём 4; потом 5, и после неё готова 1. Заготовка — алгоритм Кана из главы. Она ошибается дважды.
Первая ошибка: reading_order({2: [7]}) падает с KeyError. Соберите сначала множество всех глав — ключей и тех, что в списках.
Вторая: очередь выдаёт готовые главы в порядке, в котором они стали готовы, а нужно — наименьшую. Брать min из списка готовых верно, но в тестах десятки тысяч готовых глав сразу, и каждый min будет просматривать их все. Какая структура из главы 18 выдаёт наименьший элемент за $O(\log n)$?
Кан не говорит, какую из готовых глав брать, — подходит любая, и порядок всё равно будет правильным. Поэтому очередь готовых можно заменить любой коллекцией, и с кучей из прошлой главы получается «наименьшая из готовых» за $O(\log n)$. Всего $O((V + E) \log V)$. Так же pip или система сборки может брать из готовых задач первую по любому своему правилу: по номеру, по размеру, по алфавиту.
Возьмём станцию и найдём самую далёкую от неё: сколько до неё рёбер? Станция, у которой это число наименьшее, — центр сети: от неё до любой станции ближе всего в худшем случае. Само это наименьшее число называют радиусом графа. Напишите center(graph): верните пару (радиус, список всех центров по возрастанию). Граф без направлений и связный. Для отрезка 1 — 2 — 3 — 4 — 5 ответ (2, [3]), для отрезка из четырёх — (2, [2, 3]).
Один из тестов берёт метро из главы — load_metro() из cs.graphs. Угадайте центр, прежде чем считать. Вряд ли это «Охотный ряд». Ещё один тест — решётка 30 × 30, на неё даётся пять секунд.
Сколько рёбер до самой далёкой вершины, говорит одна волна из главы: это наибольшее значение в словаре dist.
Пустите волну из каждой вершины, запомните её «дальность», найдите наименьшую и соберите все вершины с такой дальностью. Для метро это 312 волн по тысяче шагов — мгновенно.
$V$ волн по $O(V + E)$ — всего $O(V(V + E))$. Центр московского метро в наших данных — «Шаболовская»: до любой станции не больше 17 рёбер. Центр графа не совпадает с центром карты: это точка равновесия между самыми далёкими концами. От «Шаболовской» по 17 рёбер и до «Физтеха» на севере, и до «Бунинской аллеи» и «Аэропорта Внуково» на юго-западе. От «Охотного ряда» до «Бунинской аллеи» — 20: длинные юго-западные ветки тянут центр к себе. Для сети из миллионов вершин так считать уже нельзя — там ищут центр приближённо, несколькими волнами из удачно выбранных вершин.
Куда дальше
Гипотеза шести рукопожатий почти подтвердилась для курса и провалилась на метро, и мы знаем почему: тесный мир держится на немногих дальних связях. Волна, нить и счётчики Кана пригодятся везде, где есть связи.
Но у прибора есть слепое пятно. Спросим волну, как доехать от «Сокольников» до «Москва-Сити», и сравним её ответ с дорогой через центр по минутам: время в пути мы грубо оценили по тем же данным.
Волна выбрала Большую кольцевую: десять рёбер вместо тринадцати. Но на ней два перехода вместо одного и перегоны почти вдвое длиннее, чем в центре, и по нашей грубой оценке выходит 33 минуты, а дорога через центр с тремя лишними станциями — 26. Для волны все рёбра одинаковы: короткий перегон в центре, длинный на окраине и переход по коридору — всё один шаг. У дорог есть длина, а BFS её не видит. Навигатору нужен обход, который расходится по времени, как пожар по траве: быстро там, где идти близко, медленно там, где далеко. Его придумал Эдсгер Дейкстра, и мы соберём его в главе 24 — вместе с кучей из прошлой главы, которая подскажет, какой перекрёсток ближе всего.
Сначала, впрочем, нужны два умения, без которых не обходится ни навигатор, ни почти любая программа с данными: быстро найти нужное и расставить всё по порядку. Как это делать и почему у сортировки сравнениями есть предел скорости, который не обойти никакой хитростью, — в следующей главе, на турнире сортировок.