Вівторок, 23.04.2024, 17:28

Гость

Мішатронік

Меню сайту

Наше опитування

Статистика

Онлайн всього: 1

Гостей: 1

Користувачів: 0

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

В данной статье рассматривается структура данных "система непересекающихся множеств" (на английском "disjoint-set-union", или просто "DSU").

Эта структура данных предоставляет следующие возможности. Изначально имеется несколько элементов, каждый из которых находится в отдельном (своём собственном) множестве. За одну операцию можно объединить два каких-либо множества, а также можно запросить, в каком множестве сейчас находится указанный элемент. Также, в классическом варианте, вводится ещё одна операция — создание нового элемента, который помещается в отдельное множество.

Таким образом, базовый интерфейс данной структуры данных состоит всего из трёх операций:

${\rm make\_set}(x)$ — добавляет новый элемент $x$ , помещая его в новое множество, состоящее из одного него.
${\rm union\_sets}(x,y)$ — объединяет два указанных множества (множество, в котором находится элемент $x$ , и множество, в котором находится элемент $y$ ).
${\rm find\_set}(x)$ — возвращает, в каком множестве находится указанный элемент $x$ . На самом деле при этом возвращается один из элементов множества (называемыйпредставителем или лидером (в англоязычной литературе "leader")). Этот представитель выбирается в каждом множестве самой структурой данных (и может меняться с течением времени, а именно, после вызовов ${\rm union\_sets}()$ ).
Например, если вызов ${\rm find\_set}()$ для каких-то двух элементов вернул одно и то же значение, то это означает, что эти элементы находятся в одном и том же множестве, а в противном случае — в разных множествах.

Описываемая ниже структура данных позволяет делать каждую из этих операций почти за $O(1)$ в среднем (более подробно об асимптотике см. ниже после описания алгоритма).

Также в одном из подразделов статьи описан альтернативный вариант реализации DSU, позволяющий добиться асимптотики $O(\log n)$ в среднем на один запрос при $m \ge n$ ; а при $m >> n$ (т.е. $m$ значительно больше $n$ ) — и вовсе времени $O(1)$ в среднем на запрос (см. "Хранение DSU в виде явного списка множеств").

Построение эффективной структуры данных

Определимся сначала, в каком виде мы будем хранить всю информацию.

Множества элементов мы будем хранить в виде деревьев: одно дерево соответствует одному множеству. Корень дерева — это представитель (лидер) множества.

При реализации это означает, что мы заводим массив ${\rm parent}$ , в котором для каждого элемента мы храним ссылку на его предка в дерева. Для корней деревьев будем считать, что их предок — они сами (т.е. ссылка зацикливается в этом месте).

Наивная реализация

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

Итак, вся информация о множествах элементов хранится у нас с помощью массива ${\rm parent}$ .

Чтобы создать новый элемент (операция ${\rm make\_set}(v)$ ), мы просто создаём дерево с корнем в вершине $v$ , отмечая, что её предок — это она сама.

Чтобы объединить два множества (операция ${\rm union\_sets}(a,b)$ ), мы сначала найдём лидеров множества, в котором находится $a$ , и множества, в котором находится $b$ . Если лидеры совпали, то ничего не делаем — это значит, что множества и так уже были объединены. В противном случае можно просто указать, что предок вершины $b$ равен $a$ (или наоборот) — тем самым присоединив одно дерево к другому.

Наконец, реализация операции поиска лидера ( ${\rm find\_set}(v)$ ) проста: мы поднимаемся по предкам от вершины $v$ , пока не дойдём до корня, т.е. пока ссылка на предка не ведёт в себя. Эту операцию удобнее реализовать рекурсивно (особенно это будет удобно позже, в связи с добавляемыми оптимизациями).

void make_set (int v) {
 parent[v] = v;
}
 
int find_set (int v) {
 if (v == parent[v])
 return v;
 return find_set (parent[v]);
}
 
void union_sets (int a, int b) {
 a = find_set (a);
 b = find_set (b);
 if (a != b)
 parent[b] = a;
}

Впрочем, такая реализация системы непересекающихся множеств весьма неэффективна. Легко построить пример, когда после нескольких объединений множеств получится ситуация, что множество — это дерево, выродившееся в длинную цепочку. В результате каждый вызов ${\rm find\_set}()$ будет работать на таком тесте за время порядка глубины дерева, т.е. за $O(n)$ .

Это весьма далеко от той асимптотики, которую мы собирались получить (константное время работы). Поэтому рассмотрим две оптимизации, которые позволят (даже применённые по отдельности) значительно ускорить работу.

Эвристика сжатия пути

Эта эвристика предназначена для ускорения работы ${\rm find\_set}()$ .

Она заключается в том, что когда после вызова ${\rm find\_set}(v)$ мы найдём искомого лидера $p$ множества, то запомним, что у вершины $v$ и всех пройденных по пути вершин — именно этот лидер $p$ . Проще всего это сделать, перенаправив их ${\rm parent}[]$ на эту вершину $p$ .

Таким образом, у массива предков ${\rm parent}[]$ смысл несколько меняется: теперь это сжатый массив предков, т.е. для каждой вершины там может храниться не непосредственный предок, а предок предка, предок предка предка, и т.д.

С другой стороны, понятно, что нельзя сделать, чтобы эти указатели ${\rm parent}$ всегда указывали на лидера: иначе при выполнении операции ${\rm union\_sets}()$ пришлось бы обновлять лидеров у $O(n)$ элементов.

Таким образом, к массиву ${\rm parent}[]$ следует подходить именно как к массиву предков, возможно, частично сжатому.

Новая реализация операции ${\rm find\_set}()$ выглядит следующим образом:

int find_set (int v) {
 if (v == parent[v])
 return v;
 return parent[v] = find_set (parent[v]);
}

Такая простая реализация делает всё, что задумывалось: сначала путём рекурсивных вызовов находится лидера множества, а затем, в процессе раскрутки стека, этот лидер присваивается ссылкам ${\rm parent}$ для всех пройденных элементов.

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

Оценка асимптотики при применении эвристики сжатия пути

Покажем, что применение одной эвристики сжатия пути позволяет достичь логарифмическую асимптотику: $O(\log n)$ на один запрос в среднем.

Заметим, что, поскольку операция ${\rm union\_sets}()$ представляет из себя два вызова операции ${\rm find\_set}()$ и ещё $O(1)$ операций, то мы можем сосредоточиться в доказательстве только на оценку времени работы $O(m)$ операций ${\rm find\_set}()$ .

Назовём весом $w[v]$ вершины $v$ число потомков этой вершины (включая её саму). Веса вершин, очевидно, могут только увеличиваться в процессе работы алгоритма.

Назовём размахом ребра $(a,b)$ разность весов концов этого ребра: $|w[a] - w[b]|$ (очевидно, у вершины-предка вес всегда больше, чем у вершины-потомка). Можно заметить, что размах какого-либо фиксированного ребра $(a,b)$ может только увеличиваться в процессе работы алгоритма.

Кроме того, разобьём рёбра на классы: будем говорить, что ребро имеет класс $k$ , если его размах принадлежит отрезку $[2^k; 2^{k+1}-1]$ . Таким образом, класс ребра — это число от $0$ до $\lceil \log n \rceil$ .

Зафиксируем теперь произвольную вершину $x$ и будем следить, как меняется ребро в её предка: сначала оно отсутствует (пока вершина $x$ является лидером), затем проводится ребро из $x$ в какую-то вершину (когда множество с вершиной $x$ присоединяется к другому множеству), и затем может меняться при сжатии путей в процессе вызовов ${\rm find\_path}$ . Понятно, что нас интересует асимптотика только последнего случая (при сжатии путей): все остальные случаи требуют $O(1)$ времени на один запрос.

Рассмотрим работу некоторого вызова операции ${\rm find\_set}$ : он проходит в дереве вдоль некоторого пути, стирая все рёбра этого пути и перенаправляя их в лидера.

Рассмотрим этот путь и исключим из рассмотрения последнее ребро каждого класса (т.е. не более чем по одному ребру из класса $0, 1, \ldots \lceil \log n \rceil$ ). Тем самым мы исключили $O(\log n)$ рёбер из каждого запроса.

Рассмотрим теперь все остальные рёбра этого пути. Для каждого такого ребра, если оно имеет класс $k$ , получается, что в этом пути есть ещё одно ребро класса $k$ (иначе мы были бы обязаны исключить текущее ребро, как единственного представителя класса $k$ ). Таким образом, после сжатия пути это ребро заменится на ребро класса как минимум $k+1$ . Учитывая, что уменьшаться вес ребра не может, мы получаем, что для каждой вершины, затронутой запросом $\rm find\_path$ , ребро в её предка либо было исключено, либо строго увеличило свой класс.

Отсюда мы окончательно получаем асимптотику работы $m$ запросов: $O((n+m) \log n)$ , что (при $m \ge n$ ) означает логарифмическое время работы на один запрос в среднем.

Эвристика объединения по рангу

Рассмотрим здесь другую эвристику, которая сама по себе способна ускорить время работы алгоритма, а в сочетании с эвристикой сжатия путей и вовсе способна достигнуть практически константного времени работы на один запрос в среднем.

Эта эвристика заключается в небольшом изменении работы ${\rm union\_sets}$ : если в наивной реализации то, какое дерево будет присоединено к какому, определяется случайно, то теперь мы будем это делать на основе рангов.

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

В обоих вариантах суть эвристики одна и та же: при выполнении $\rm union\_sets$ будем присоединять дерево с меньшим рангом к дереву с большим рангом.

Приведём реализацию ранговой эвристики на основе размеров деревьев:

void make_set (int v) {
 parent[v] = v;
 size[v] = 1;
}
 
void union_sets (int a, int b) {
 a = find_set (a);
 b = find_set (b);
 if (a != b) {
 if (size[a] < size[b])
 swap (a, b);
 parent[b] = a;
 size[a] += size[b];
 }
}

Приведём реализацию ранговой эвристики на основе глубины деревьев:

void make_set (int v) {
 parent[v] = v;
 rank[v] = 0;
}
 
void union_sets (int a, int b) {
 a = find_set (a);
 b = find_set (b);
 if (a != b) {
 if (rank[a] < rank[b])
 swap (a, b);
 parent[b] = a;
 if (rank[a] == rank[b])
 ++rank[a];
 }
}

Оба варианта ранговой эвристики являются эквивалентными с точки зрения асимптотики, поэтому на практике можно применять любую из них.

Оценка асимптотики при применении ранговой эвристики

Покажем, что асимптотика работы системы непересекающихся множеств при использовании только ранговой эвристики, без эвристики сжатия путей, будет логарифмической на один запрос в среднем: $O (\log n)$ .

Здесь мы покажем, что при любом из двух вариантов ранговой эвристики глубина каждого дерева будет величиной $O (\log n)$ , что автоматически будет означать логарифмическую асимптотику для запроса $\rm find\_set$ , и, следовательно, запроса $\rm union\_sets$ .

Рассмотрим ранговую эвристику по глубине дерева. Покажем, что если ранг дерева равен $k$ , то это дерево содержит как минимум $2^k$ вершин (отсюда будет автоматически следовать, что ранг, а, значит, и глубина дерева, есть величина $O(\log n)$ ). Доказывать будем по индукции: для $k=0$ это очевидно. При сжатии путей глубина может только уменьшиться. Ранг дерева увеличивается с $k-1$ до $k$ , когда к нему присоединяется дерево ранга $k-1$ ; применяя к этим двум деревьям размера $k-1$ предположение индукции, получаем, что новое дерево ранга $k$ действительно будет иметь как минимум $2^k$ вершин, что и требовалось доказать.

Рассмотрим теперь ранговую эвристику по размерам деревьев. Покажем, что если размер дерева равен $k$ , то его высота не более $\lfloor \log k \rfloor$ . Доказывать будем по индукции: для $k=1$ утверждение верно. При сжатии путей глубина может только уменьшиться, поэтому сжатие путей ничего не нарушает. Пусть теперь объединяются два дерева размеров $k_1$ и $k_2$ ; тогда по предположению индукции их высоты меньше либо равны, соответственно, $\lfloor \log k_1 \rfloor$ и $\lfloor \log k_2 \rfloor$ . Не теряя общности, считаем, что первое дерево — большее ( $k_1 \ge k_2$ ), поэтому после объединения глубина получившегося дерева из $k_1+k_2$ вершин станет равна: