Система непересекающихся множеств

Представьте, что после снегопада все улицы центра Алматы закрыты и открываются по одной, в случайном порядке. Пока открыто мало, город распадается на острова: два-три перекрёстка, связанных расчищенной улицей, а вокруг — непроезжие. Каждая новая улица либо сливает два острова в один, либо замыкает круг внутри острова и ничего не меняет. Вопрос, который задают снова и снова: на одном ли острове эти два перекрёстка? Ниже — 7909 перекрёстков и 10 423 куска улиц из OpenStreetMap. Острова раскрашены, самый большой — цветом раздела. Следите за графиком: долго почти ничего не происходит, а потом город срастается рывком.

При случайном порядке самый большой остров долго остаётся крошечным: на половине открытых улиц в нём 110 перекрёстков, на 70% — 1574. А следующие десять процентов улиц раздувают его до 5630 перекрёстков — больше двух третей города. Половину города он накрывает на 8040-й улице из 10 423, то есть на 77,1%. Если открывать сначала проспекты, а потом улицы помельче, половина города связана уже на 45,2% улиц: магистрали — это скелет, на который нанизаны кварталы. А если открывать от коротких к длинным, рывок случается ещё позже, на 83,5%.

Резкий переход называют перколяцией, от латинского «просачиваться»: так вода находит путь сквозь пористый камень, когда открытых пор становится достаточно. Для квадратной решётки, где у каждого узла четыре соседа, порог ровно половина связей — это доказал Харри Кестен в 1980 году. У городского перекрёстка в среднем 2,6 улицы, каждый шестой перекрёсток — тупик, и порог выше. Вся кривая на графике получена одним проходом: улицы добавляются по одной, и структура после каждой сразу знает число островов и размер самого большого. Её устройство — тема этой статьи.

Идея

Каждое множество — дерево, где каждый элемент помнит только своего родителя, а корень — само себе родитель и служит именем множества. Узнать, в каком множестве элемент, — подняться по родителям до корня. Слить два множества — подвесить корень одного под корень другого. Чтобы деревья оставались низкими, меньшее дерево вешают под большее, а при каждом подъёме к корню перевешивают пройденные элементы поближе к корню.

Операций две: find(x) возвращает корень множества, где лежит x, и union(a, b) сливает множества a и b. Элементы «в одном множестве», если find у них одинаковый. Весь лес — один массив parent: parent[x] — родитель x, у корня parent[x] = x. На улицах Алматы элемент — перекрёсток, множество — остров, а открытая улица (a, b) — вызов union(a, b). Если find(a) и find(b) совпали ещё до слияния, улица замкнула круг.

Обратите внимание, чего структура не умеет. Она не помнит, какими улицами связаны перекрёстки, и не может разрезать множество обратно. Поиск в ширину или в глубину тоже находит связные куски графа, но каждый раз заново, за O(V + E). Система непересекающихся множеств хороша там, где связи только добавляются, а вопросы перемежаются с добавлениями. Знакомство с ней на примере электрификации Моравии — в главе курса «Жадность и электричество».

Почему дерево вырастает в палку

Если сливать как попало, лес может выродиться. Возьмите шестнадцать элементов и слейте (1, 0), (2, 1), …, (15, 14), каждый раз подвешивая старый корень под новичка: получится цепочка, и find(0) пройдёт все пятнадцать шагов. Кнопка «Цепочка» ниже строит именно её. Потом переключите слияние на «по размеру» и нажмите «Цепочку» ещё раз — или оставьте цепочку и выберите сжатие: коснитесь элемента 0 дважды, и find выпрямит путь.

Против вырождения есть два приёма, и они дополняют друг друга.

Слияние по размеру. В корне храним размер дерева и при слиянии вешаем меньшее дерево под корень большего. Вариант — слияние по рангу, где вместо размера хранят оценку высоты; оценки у них одинаковые. На цепочке из примера по размеру получается звезда: каждый новый элемент встаёт прямо под корень.

Сжатие путей. Раз уж find прошёл путь до корня, перевесим пройденные элементы поближе к нему. Полное сжатие делает два прохода: найти корень, потом подвесить на него всех с пути. Сжатие через ступеньку обходится одним проходом: каждый элемент на пути перевешивается на своего деда, parent[x] = parent[parent[x]], и путь укорачивается примерно вдвое. Оценки у обоих вариантов одинаковые, а через ступеньку проще и не требует рекурсии.

Программа dsu из раздела с кодом считает, сколько стоят приёмы на 4096 элементах. На цепочке без приёмов самый глубокий элемент лежит на глубине 4095, а find для каждого из 4096 элементов в сумме проходит 8 386 560 шагов — по 2048 на вызов. Слияние по размеру превращает ту же цепочку в звезду: 4095 шагов на все вызовы, по одному. Одно сжатие через ступеньку, без размеров, оставляет цепочку длиной 4095, но первые же вызовы find её сплющивают: все 4096 вызовов вместе — 10 111 шагов. Для слияния по размеру худший порядок другой — турнир: слить пары, потом пары пар и так далее. Глубина тогда 12 = log₂ 4096, и это предел, как доказано ниже.

Почему так быстро

Без слияния по размеру это неверно — цепочка из примера тому доказательство. Сжатие путей в одиночку тоже даёт логарифм, но только в среднем по последовательности операций: отдельный find может пройти длинный путь, зато после него путь станет коротким, и дорогой вызов как бы оплачивает дешевизну следующих. Такой счёт называют амортизационным.

Вместе два приёма дают оценку, которая долго не давалась доказательству. В 1973 году Джон Хопкрофт и Джеффри Ульман показали, что m операций над n элементами стоят O(m log* n), где log* n — сколько раз нужно взять двоичный логарифм, чтобы дойти до единицы: для числа 2⁶⁵⁵³⁶, в котором почти двадцать тысяч десятичных знаков, log* равен пяти. В 1975 году Роберт Тарьян доказал точную оценку O(m α(m, n)), где α — обратная функция Аккермана. Функция Аккермана растёт быстрее любой башни степеней, а обратная к ней — медленнее любого повторного логарифма: для любого числа элементов, которое поместится в память любого компьютера, α не больше 4. Улучшить эту оценку нельзя: в 1989 году Майкл Фредман и Майкл Сакс доказали, что любая структура для этой задачи в худшем случае тратит на операцию в среднем не меньше порядка α — и это не про лес с родителями, а про любой способ хранения.

Код

Класс — два массива и две операции. Сжатие через ступеньку — одна строка в цикле find; рекурсия не нужна, и на цепочке в сотни тысяч элементов программа не упрётся в предел глубины стека. Кроме класса, программа ставит опыт из раздела выше: строит лес двумя порядками слияний — цепочкой и турниром — с приёмами и без и считает шаги.

Обратите внимание на массив parent в первом примере: у элемента 7 родитель 6, а не корень 4. Слияние не трогает элементы внутри деревьев, а сжатие путей перевешивает только тех, через кого прошёл find. Лес никогда не бывает «идеально плоским», и это не нужно: он плоский там, где по нему ходят.

А это первая сцена программой: настоящий граф улиц, три порядка открытия и таблица, по которой построен график. Перемешивание — алгоритм Фишера — Йетса со своим генератором, поэтому порядок улиц совпадает в Python, Go и в сцене.

Последняя строка вывода — подсказка к соседней статье. При порядке «от коротких к длинным» каждая улица, которая сливает два острова, — ребро минимального остовного дерева графа улиц, а вся программа — алгоритм Краскала. Последняя такая улица длиной 3053 метра — самое длинное ребро этого дерева.

Удалять нельзя — поверните время

У структуры есть принципиальное ограничение: слитое обратно не разрезать. Корень одного дерева висит под корнем другого, а какая улица их соединила, никто не запомнил. Поэтому вопрос «город расчищали после снегопада — когда острова слились?» решается сразу, а обратный — «улицы перекрывают одну за другой — когда город распадётся?» — нет. Отмотайте график в сцене назад: она каждый раз строит лес заново с нуля, потому что откатить слияние не может.

Если список перекрытий известен заранее, есть выход: прочитать его с конца. Начнём с города, в котором уже закрыто всё, что будет закрыто, и станем открывать улицы в обратном порядке. Каждое перекрытие, прочитанное задом наперёд, — слияние, и ответы на вопросы получаются тоже задом наперёд; останется их развернуть. Это частый приём обработки запросов не по порядку — офлайн, — и на нём построена задача о перекрытиях улиц. В её тестах — тот же Алматы: если перекрывать улицы в случайном порядке, город распадается уже на восьмом перекрытии (тупиков много), а если перекрыть все 2616 кусков крупных дорог, остаётся 1472 отдельных части. Когда перекрытия приходят по одному и отвечать нужно сразу, нужны куда более сложные структуры динамической связности: лучшие известные детерминированные — Холма, де Лихтенберга и Торупа (2001) — тратят на изменение O(log² n) в среднем по последовательности.

Есть и промежуточный вариант — откат последних слияний, как кнопка «отменить» в редакторе. Если отказаться от сжатия путей и оставить только слияние по размеру, каждое слияние меняет две ячейки — родителя одного корня и размер другого, — их можно запомнить в стеке и вернуть. Глубина при этом остаётся логарифмической по теореме выше. На откатах держатся офлайн-алгоритмы, которые перебирают отрезки времени, когда каждое ребро существует.

Сколько это стоит

Память — два массива по n чисел: родитель и размер (размер нужен только корням). На настоящих данных счёт ещё скромнее, чем обещают оценки. Посмотрите на последний счётчик первой сцены: пока открывается весь город, find вызывается 20 846 раз — по два на улицу — и при случайном порядке проходит всего 12 418 шагов, в среднем 0,6 шага на вызов; при двух других порядках — почти столько же. Большинство вызовов застают элемент прямо у корня или в одном шаге от него.

Типичная задача — связные куски графа, рёбра которого приходят потоком. Сравните с обходом: поиск в ширину находит компоненты за O(V + E), но после каждого нового ребра его пришлось бы запускать заново, и на 10 423 улицах Алматы это десять тысяч обходов города. Система непересекающихся множеств отвечает на тот же вопрос после каждой улицы, и весь график в сцене стоит один проход.

Где работает

• Минимальное остовное дерево. Алгоритм Краскала перебирает рёбра от лёгких к тяжёлым и берёт ребро, если find у концов разный, — ровно программа city с порядком «короткие первыми».
• Разметка областей на изображениях. Функция measure.label из scikit-image, которая нумерует связные пятна на снимке, хранит метки в массиве-лесу — в её исходнике есть и find_root, и сжатие путей. Задача о тёмных островах — то же на фотографии.
• Физика перколяции. Алгоритм Хошена — Копельмана (1976) размечает кластеры на решётке тем же способом, а метод Ньюмана — Циффа (2000) добавляет связи по одной и получает всю кривую сразу — как график в нашей сцене.
• Компиляторы. С них всё началось: переменные, которые объявлены как занимающие одну память, образуют классы эквивалентности, и компилятору нужно знать эти классы целиком.
• Лабиринты. Случайный Краскал: перебирать стенки между клетками в случайном порядке и ломать стенку, если клетки по разные стороны ещё не связаны. Получается лабиринт, где между любыми двумя клетками ровно один путь.

Сорок процентов на объявлениях Фортрана

В Фортране и похожих языках шестидесятых можно было объявить, что две переменные или два массива занимают одну и ту же память: оператор EQUIVALENCE. Объявления цепляются друг за друга — A с B, B с C, — и компилятору нужно собрать из них классы эквивалентности и раздать каждому классу место в памяти. В мае 1964 года Бернард Галлер и Майкл Фишер опубликовали в Communications of the ACM заметку «An improved equivalence algorithm». Алгоритм был основан на древовидной структуре и, как сказано в аннотации, находил все классы эквивалентности за один просмотр объявлений, сократив время на 40 процентов по сравнению с опубликованным ранее способом. Это и был лес с родителями.

Дальше структура стала любимым испытательным полигоном теории. Хопкрофт и Ульман в 1973 году доказали оценку через log*, Тарьян в 1975-м — точную оценку через обратную функцию Аккермана, а в 1979-м показал, что широкий класс алгоритмов на указателях быстрее работать не может. В 1984 году Тарьян и Ян ван Леувен разобрали все варианты сжатия, включая «через ступеньку». Независимо от информатиков физики Джозеф Хошен и Рауль Копельман в 1976 году придумали тот же приём для подсчёта кластеров в задачах о перколяции.

Задачи

В первой задаче тёмные пятна на фотографии сливаются по мере того, как растёт порог яркости, — нужен счёт островов после каждого шага. Во второй улицы Алматы не открываются, а перекрываются, и придётся повернуть время.