Структура данных непересекающегося множества

Структура данных для хранения непересекающихся наборов

В информатике структура данных непересекающихся множеств , также называемая структурой данных «объединение–поиск» или «слияние–поиск множеств» , представляет собой структуру данных , которая хранит коллекцию непересекающихся (непересекающихся) множеств . Эквивалентно, она хранит разбиение множества на непересекающиеся подмножества . Она предоставляет операции для добавления новых множеств, слияния множеств (замены их их объединением ) и поиска представительного члена множества. Последняя операция позволяет эффективно выяснить, находятся ли любые два элемента в одном и том же или разных множествах.

Хотя существует несколько способов реализации структур данных непересекающихся множеств, на практике они часто отождествляются с конкретной реализацией, называемой лесом непересекающихся множеств . Это специализированный тип леса , который выполняет объединения и поиск за почти постоянное амортизированное время . Для выполнения последовательности из m операций сложения, объединения или поиска в лесу непересекающихся множеств с n узлами требуется общее время O ( m α( n )) , где α( n ) — чрезвычайно медленно растущая обратная функция Аккермана . Леса непересекающихся множеств не гарантируют такую ​​производительность на основе каждой операции. Отдельные операции объединения и поиска могут занять больше времени, чем константа, умноженная на α( n ) , но каждая операция заставляет лес непересекающихся множеств подстраиваться так, чтобы последующие операции выполнялись быстрее. Леса непересекающихся множеств являются как асимптотически оптимальными , так и практически эффективными.

Структуры данных непересекающихся множеств играют ключевую роль в алгоритме Краскала для поиска минимального остовного дерева графа. Важность минимальных остовных деревьев означает, что структуры данных непересекающихся множеств лежат в основе широкого спектра алгоритмов. Кроме того, структуры данных непересекающихся множеств также имеют приложения к символьным вычислениям, а также в компиляторах, особенно для задач распределения регистров .

История

Леса непересекающихся множеств были впервые описаны Бернардом А. Галлером и Майклом Дж. Фишером в 1964 году. ^[2] В 1973 году их временная сложность была ограничена до , итерированного логарифма , Хопкрофтом и Ульманом . [ ^3] В 1975 году Роберт Тарьян был первым, кто доказал верхнюю границу ( обратную функцию Аккермана ) временной сложности алгоритма. ^[4] Он также доказал, что она узкая. В 1979 году он показал, что это нижняя граница для определенного класса алгоритмов, которые включают структуру Галлера-Фишера. ^[5] В 1989 году Фредман и Сакс показали, что (амортизированные) слова битов должны быть доступны любой структуре данных непересекающихся множеств за одну операцию, ^[6] тем самым доказав оптимальность структуры данных в этой модели. ${\displaystyle O(\log ^{*}(n))}$ ${\displaystyle n}$ ${\displaystyle O(m\alpha (n))}$ ${\displaystyle \Omega (\alpha (n))}$ ${\displaystyle O(\log n)}$

В 1991 году Галил и Итальяно опубликовали обзор структур данных для непересекающихся множеств. ^[7]

В 1994 году Ричард Дж. Андерсон и Хизер Уолл описали параллельную версию Union–Find, которая никогда не должна блокироваться. ^[8]

В 2007 году Сильвен Коншон и Жан-Кристоф Филлиатр разработали полуперсистентную версию структуры данных непересекающегося леса и формализовали ее корректность с помощью помощника доказательства Coq . ^[9] «Полуперсистентный» означает, что предыдущие версии структуры эффективно сохраняются, но доступ к предыдущим версиям структуры данных делает более поздние недействительными. Их самая быстрая реализация достигает производительности почти такой же эффективной, как и неперсистентный алгоритм. Они не выполняют анализ сложности.

Также были рассмотрены варианты непересекающихся структур данных с лучшей производительностью на ограниченном классе задач. Габов и Тарьян показали, что если возможные объединения ограничены определенным образом, то возможен действительно линейный алгоритм времени. ^[10]

Представление

Каждый узел в непересекающемся лесу состоит из указателя и некоторой вспомогательной информации, либо размера, либо ранга (но не того и другого). Указатели используются для создания родительских деревьев указателей , где каждый узел, который не является корнем дерева, указывает на своего родителя. Чтобы отличить корневые узлы от других, их родительские указатели имеют недопустимые значения, такие как циклическая ссылка на узел или контрольное значение. Каждое дерево представляет набор, хранящийся в лесу, причем членами набора являются узлы в дереве. Корневые узлы предоставляют представителей наборов: два узла находятся в одном наборе тогда и только тогда, когда корни деревьев, содержащих узлы, равны.

Узлы в лесу могут храниться любым удобным для приложения способом, но распространенным методом является хранение их в массиве. В этом случае родители могут быть указаны их индексом массива. Каждая запись массива требует Θ(log n ) бит памяти для родительского указателя. Для остальной части записи требуется сопоставимый или меньший объем памяти, поэтому количество бит, требуемых для хранения леса, составляет Θ( n log n ) . Если реализация использует узлы фиксированного размера (тем самым ограничивая максимальный размер леса, который может быть сохранен), то необходимое хранилище линейно зависит от n .

Операции

Структуры данных непересекающихся множеств поддерживают три операции: создание нового множества, содержащего новый элемент; поиск представителя множества, содержащего заданный элемент; и слияние двух множеств.

Создание новых наборов

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

В непересекающемся лесу MakeSetинициализирует родительский указатель узла и размер или ранг узла. Если корень представлен узлом, который указывает на себя, то добавление элемента можно описать с помощью следующего псевдокода:

функция MakeSet( x ) —  если  x еще не находится в лесу , то  x .parent := x  x .size := 1 // если узлы хранят размер  x .rank := 0 // если узлы хранят ранг  end if end function

Эта операция имеет постоянную временную сложность. В частности, инициализация непересекающегося леса с n узлами требует O ( n ) времени.

Отсутствие назначенного узлу родителя означает, что узел отсутствует в лесу.

На практике, MakeSetдолжна предшествовать операция, которая выделяет память для хранения x . Пока выделение памяти является амортизированной постоянной операцией времени, как это происходит для хорошей реализации динамического массива , это не изменяет асимптотическую производительность леса случайных множеств.

Поиск представителей набора

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

Выполнение Findоперации представляет собой важную возможность для улучшения леса. Время в Findоперации тратится на погоню за родительскими указателями, поэтому более плоское дерево приводит к более быстрым Findоперациям. Когда Findвыполняется a, нет более быстрого способа достичь корня, чем следовать каждому родительскому указателю последовательно. Однако родительские указатели, посещенные во время этого поиска, могут быть обновлены, чтобы указывать ближе к корню. Поскольку каждый элемент, посещенный на пути к корню, является частью одного и того же набора, это не изменяет наборы, хранящиеся в лесу. Но это ускоряет будущие Findоперации не только для узлов между узлом запроса и корнем, но и для их потомков. Это обновление является важной частью амортизированной гарантии производительности леса непересекающихся наборов.

Существует несколько алгоритмов Find, которые достигают асимптотически оптимальной временной сложности. Одно семейство алгоритмов, известное как сжатие пути , делает каждый узел между узлом запроса и корнем указателем на корень. Сжатие пути может быть реализовано с помощью простой рекурсии следующим образом:

функция Find( x ) —  если  x .parent ≠ x  , то  x .parent := Find( x .parent) возвращает  x .parent иначе  возвращает  x  конец, если функция end

Эта реализация делает два прохода, один вверх по дереву и один обратно вниз. Она требует достаточно рабочей памяти для хранения пути от узла запроса к корню (в приведенном выше псевдокоде путь неявно представлен с помощью стека вызовов). Это можно уменьшить до постоянного объема памяти, выполнив оба прохода в одном направлении. Реализация постоянной памяти проходит от узла запроса к корню дважды, один раз для поиска корня и один раз для обновления указателей:

функция Find( x ) is  root  := x  while  root .parent ≠ root  do  root  := root .parent end while пока  x .parent ≠ root  do  parent  := x .parent x .parent := root  x  := parent  end while  функция возврата корня конца

Тарьян и Ван Лиувен также разработали однопроходные Findалгоритмы, которые сохраняют ту же самую сложность в худшем случае, но более эффективны на практике. ^[4] Они называются расщеплением пути и делением пути пополам. Оба они обновляют родительские указатели узлов на пути между узлом запроса и корнем. Расщепление пути заменяет каждый родительский указатель на этом пути указателем на прародителя узла:

функция Find( x ) is  while  x .parent ≠ x  do ( x , x .parent) := ( x .parent, x .parent.parent) end while  return  x end function

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

функция Find( x ) is  while  x .parent ≠ x  do  x .parent := x .parent.parent x  := x .parent end while  return  x end function

Объединение двух наборов

MakeSetсоздает 8 синглтонов.

После некоторых операций Unionнекоторые множества группируются вместе.

Операция заменяет множество, содержащее x , и множество, содержащее y , их объединением. first используется для определения корней деревьев, содержащих x и y . Если корни одинаковы, то больше ничего делать не нужно. В противном случае два дерева должны быть объединены. Это делается либо установкой родительского указателя корня x на y , либо установкой родительского указателя корня y на x .Union(x, y)UnionFind

Выбор того, какой узел станет родительским, влияет на сложность будущих операций на дереве. Если это сделать небрежно, деревья могут стать чрезмерно высокими. Например, предположим, что Unionвсегда делал дерево, содержащее x, поддеревом дерева, содержащего y . Начнем с леса, который только что был инициализирован элементами , и выполним , , ..., . Полученный лес содержит единственное дерево, корень которого n , а путь от 1 до n проходит через каждый узел в дереве. Для этого леса время выполнения составляет O ( n ) . ${\displaystyle 1,2,3,\ldots ,n,}$Union(1, 2)Union(2, 3)Union(n - 1, n)Find(1)

В эффективной реализации высота дерева контролируется с помощью union by size или union by rank . Оба варианта требуют, чтобы узел хранил информацию, помимо указателя на родителя. Эта информация используется для принятия решения о том, какой корень станет новым родителем. Обе стратегии гарантируют, что деревья не станут слишком глубокими.

Объединение по размеру

В случае объединения по размеру узел сохраняет свой размер, который является просто числом его потомков (включая сам узел). Когда деревья с корнями x и y объединяются, узел с большим числом потомков становится родителем. Если два узла имеют одинаковое число потомков, то любой из них может стать родителем. В обоих случаях размер нового родительского узла устанавливается равным его новому общему числу потомков.

функция Union( x , y ) is  // Заменить узлы корнями  x  := Find( x ) y  := Find( y ) если  x = y  тогда  return  // x и y уже находятся в одном и том же множестве  end if // При необходимости поменяйте местами переменные, чтобы гарантировать, что  // x имеет по крайней мере столько же потомков, сколько и y  if  x .size < y .size then ( x , y ) := ( y , x ) end if // Сделать x новым корнем  y .parent := x  // Обновить размер x  x .size := x .size + y .size end function

Число бит, необходимое для хранения размера, очевидно, равно числу бит, необходимому для хранения n . Это добавляет постоянный фактор к требуемому объему памяти леса.

Союз по рангу

Для объединения по рангу узел сохраняет свой ранг , который является верхней границей его высоты. Когда узел инициализируется, его ранг устанавливается равным нулю. Чтобы объединить деревья с корнями x и y , сначала сравните их ранги. Если ранги различны, то дерево с большим рангом становится родителем, а ранги x и y не изменяются. Если ранги одинаковы, то любой из них может стать родителем, но ранг нового родителя увеличивается на единицу. Хотя ранг узла явно связан с его высотой, хранение рангов более эффективно, чем хранение высот. Высота узла может меняться во время операции Find, поэтому хранение рангов позволяет избежать дополнительных усилий по поддержанию правильной высоты. В псевдокоде объединение по рангу выглядит следующим образом:

функция Union( x , y ) is  // Заменить узлы корнями  x  := Find( x ) y  := Find( y ) если  x = y  тогда  return  // x и y уже находятся в одном и том же множестве  end if // При необходимости переименуйте переменные, чтобы гарантировать, что  // x имеет ранг не меньше, чем у y  if  x .rank < y .rank then ( x , y ) := ( y , x ) end if // Сделать x новым корнем  y .parent := x  // При необходимости увеличить ранг x  if  x .rank = y .rank then  x .rank := x .rank + 1 end if end function

Можно показать, что каждый узел имеет ранг или меньше. ^[11] Следовательно, каждый ранг может быть сохранен в O (log log n ) бит, а все ранги могут быть сохранены в O ( n log log n ) бит. Это делает ранги асимптотически пренебрежимо малой частью размера леса. ${\displaystyle \lfloor \log n\rfloor }$

Из приведенных выше реализаций ясно, что размер и ранг узла не имеют значения, если только узел не является корнем дерева. Как только узел становится дочерним, его размер и ранг больше никогда не будут доступны.

Сложность времени

Реализация леса с непересекающимися множествами Find, в которой не обновляются родительские указатели и Unionне делается попыток контролировать высоту деревьев, может иметь деревья высотой O ( n ) . В такой ситуации операции Findи Unionтребуют O ( n ) времени.

Если реализация использует только сжатие пути, то последовательность из n MakeSet операций, за которой следуют до n − 1 Union операций и f Find операций, имеет худшее время выполнения . ^[11] ${\displaystyle \Theta (n+f\cdot \left(1+\log _{2+f/n}n\right))}$

Использование объединения по рангу, но без обновления родительских указателей во время Find, дает время выполнения for m операций любого типа, до n из которых являются операциями. ^[11] ${\displaystyle \Theta (m\log n)}$MakeSet

Комбинация сжатия пути, разбиения или деления пополам с объединением по размеру или по рангу сокращает время выполнения для m операций любого типа, до n из которых являются MakeSetоперациями, до . ^{[4] [5]} Это делает амортизированное время выполнения каждой операции . Это асимптотически оптимально, что означает, что каждая структура данных непересекающегося множества должна использовать амортизированное время на операцию. ^[6] Здесь функция является обратной функцией Аккермана . Обратная функция Аккермана растет необычайно медленно, поэтому этот коэффициент равен 4 или меньше для любого n , которое фактически может быть записано в физической вселенной. Это делает операции непересекающегося множества практически амортизированными за постоянное время. ${\displaystyle \Theta (m\alpha (n))}$ ${\displaystyle \Theta (\alpha (n))}$ ${\displaystyle \Omega (\alpha (n))}$ ${\displaystyle \alpha (n)}$

Доказательство временной сложности O(m log* n) для Union-Find

Точный анализ производительности непересекающегося леса довольно сложен. Однако существует гораздо более простой анализ, который доказывает, что амортизированное время для любых m Find или Unionопераций в непересекающемся лесу, содержащем n объектов, равно O ( m log ^* n ) , где log ^* обозначает итерированный логарифм . ^{[12] [13] [14] [15]}

Лемма 1: По мере того, как функция find следует по пути к корню, ранг узла, с которым она сталкивается, увеличивается.

Доказательство

Мы утверждаем, что при применении операций Find и Union к набору данных этот факт остается верным с течением времени. Изначально, когда каждый узел является корнем своего собственного дерева, это тривиально верно. Единственный случай, когда ранг узла может быть изменен, — это когда применяется операция Union by Rank. В этом случае дерево с меньшим рангом будет присоединено к дереву с большим рангом, а не наоборот. И во время операции find все посещенные по пути узлы будут присоединены к корню, который имеет больший ранг, чем его потомки, поэтому эта операция также не изменит этот факт.

Лемма 2: Узел u , являющийся корнем поддерева ранга r, имеет по крайней мере узлов. ${\displaystyle 2^{r}}$

Доказательство

Изначально, когда каждый узел является корнем своего собственного дерева, это тривиально верно. Предположим, что узел u с рангом r имеет не менее 2 ^r узлов. Затем, когда два дерева с рангом r объединяются с помощью операции Union by Rank, получается дерево с рангом r + 1 , корень которого имеет не менее узлов. ${\displaystyle 2^{r}+2^{r}=2^{r+1}}$

Лемма 3: Максимальное количество узлов ранга r не превышает ${\displaystyle {\frac {n}{2^{r}}}.}$

Доказательство

Из леммы 2 мы знаем, что узел u, являющийся корнем поддерева с рангом r, имеет не менее узлов. Мы получим максимальное количество узлов ранга r , когда каждый узел с рангом r является корнем дерева, имеющего ровно узлов. В этом случае количество узлов ранга r равно ${\displaystyle 2^{r}}$ ${\displaystyle 2^{r}}$ ${\displaystyle {\frac {n}{2^{r}}}.}$

В любой конкретной точке выполнения мы можем сгруппировать вершины графа в «корзины» в соответствии с их рангом. Мы определяем диапазоны корзин индуктивно следующим образом: Корзина 0 содержит вершины ранга 1. Корзина 1 содержит вершины рангов 2 и 3. В общем случае, если B - я корзина содержит вершины с рангами из интервала , то (B+1)-я корзина будет содержать вершины с рангами из интервала ${\displaystyle \left[r,2^{r}-1\right]=[r,R-1]}$ ${\displaystyle \left[R,2^{R}-1\right].}$

Для пусть . Тогда ведро будет иметь вершины с рангами в интервале . ${\displaystyle B\in \mathbb {N} }$ ${\displaystyle {\text{tower}}(B)=\underbrace {2^{2^{\cdots ^{2}}}} _{B{\text{ times}}}}$ ${\displaystyle B}$ ${\displaystyle [{\text{tower}}(B),{\text{tower}}(B)-1]}$

Доказательство находки Союза ${\displaystyle O(\log ^{*}n)}$

Мы можем сделать два замечания относительно размеров ведер.

1. Общее количество сегментов не превышает log ^* n .

   Доказательство: Поскольку ни одна вершина не может иметь ранг больше , только первые блоки могут иметь вершины, где обозначает обратную функцию определенной выше. ${\displaystyle n}$ ${\displaystyle \log ^{*}(n)}$ ${\displaystyle \log ^{*}}$ ${\displaystyle {\text{tower}}}$

2. Максимальное количество элементов в контейнере — не более . ${\displaystyle \left[B,2^{B}-1\right]}$ ${\displaystyle {\frac {2n}{2^{B}}}}$

   Доказательство: Максимальное количество элементов в корзине не превышает ${\displaystyle \left[B,2^{B}-1\right]}$ ${\displaystyle {\frac {n}{2^{B}}}+{\frac {n}{2^{B+1}}}+{\frac {n}{2^{B+2}}}+\cdots +{\frac {n}{2^{2^{B}-1}}}\leq {\frac {2n}{2^{B}}}.}$

Пусть F представляет собой список выполненных операций «поиска», и пусть

$${\displaystyle T_{1}=\sum _{F}{\text{(link to the root)}}}$$ $${\displaystyle T_{2}=\sum _{F}{\text{(number of links traversed where the buckets are different)}}}$$ $${\displaystyle T_{3}=\sum _{F}{\text{(number of links traversed where the buckets are the same).}}}$$

Тогда общая стоимость m находок составит ${\displaystyle T=T_{1}+T_{2}+T_{3}.}$

Поскольку каждая операция поиска совершает ровно один обход, который приводит к корню, мы имеем T ₁ = O ( m ) .

Кроме того, из приведенной выше границы количества блоков следует, что T ₂ = O ( m log ^* n ) .

Для T ₃ предположим, что мы проходим по ребру от u до v , где u и v имеют ранг в корзине [ B , 2 ^B − 1] и v не является корнем (во время этого прохода, в противном случае проход учитывался бы в T ₁ ). Зафиксируем u и рассмотрим последовательность , которая играет роль v в различных операциях поиска. Из-за сжатия пути и отсутствия учета ребра к корню эта последовательность содержит только разные узлы, и из-за леммы 1 мы знаем, что ранги узлов в этой последовательности строго возрастают. Поскольку оба узла находятся в корзине, мы можем заключить, что длина k последовательности (количество раз, когда узел u присоединен к другому корню в той же корзине) не превышает числа рангов в корзинах B , то есть не более ${\displaystyle v_{1},v_{2},\ldots ,v_{k}}$ ${\displaystyle 2^{B}-1-B<2^{B}.}$

Поэтому, ${\displaystyle T_{3}\leq \sum _{[B,2^{B}-1]}\sum _{u}2^{B}.}$

Из наблюдений 1 и 2 можно сделать вывод, что ${\textstyle T_{3}\leq \sum _{B}2^{B}{\frac {2n}{2^{B}}}\leq 2n\log ^{*}n.}$

Поэтому, ${\displaystyle T=T_{1}+T_{2}+T_{3}=O(m\log ^{*}n).}$

Другие структуры

Лучшее время на операцию в худшем случае

Худшее время операции Findв деревьях с объединением по рангу или объединением по весу равно (т. е. оно равно и эта граница жесткая). В 1985 году Н. Блюм дал реализацию операций, которая не использует сжатие пути, но сжимает деревья в течение . Его реализация выполняется за время на операцию, ^[16] и, таким образом, по сравнению со структурой Галлера и Фишера она имеет лучшее худшее время на операцию, но худшее амортизированное время. В 1999 году Альструп и др. дали структуру, которая имеет оптимальное худшее время вместе с амортизированным временем обратного Аккермана. ^[17] ${\displaystyle \Theta (\log n)}$ ${\displaystyle O(\log n)}$ ${\displaystyle union}$ ${\displaystyle O(\log n/\log \log n)}$ ${\displaystyle O(\log n/\log \log n)}$

Удаление

Обычная реализация в виде непересекающихся лесов не реагирует благоприятно на удаление элементов, в том смысле, что время для Findне улучшится в результате уменьшения количества элементов. Однако существуют современные реализации, которые допускают удаление за постоянное время и где ограничение по времени для Findзависит от текущего количества элементов ^{[18] [19]}

Приложения

Демонстрация Union-Find при использовании алгоритма Крускала для поиска минимального остовного дерева.

Структуры данных непересекающихся множеств моделируют разбиение множества , например, для отслеживания связанных компонентов неориентированного графа . Затем эту модель можно использовать для определения того, принадлежат ли две вершины одному и тому же компоненту или приведет ли добавление ребра между ними к циклу. Алгоритм Union–Find используется в высокопроизводительных реализациях объединения . ^[20]

Эта структура данных используется библиотекой Boost Graph для реализации ее функциональности Incremental Connected Components. Она также является ключевым компонентом в реализации алгоритма Крускала для поиска минимального остовного дерева графа.

Алгоритм Хошена-Копельмана использует в своей работе метод Union-Find.

Смотрите также

• Уточнение разделов , другая структура данных для поддержки непересекающихся наборов, с обновлениями, которые разделяют наборы, а не объединяют их вместе
• Динамическое подключение

Ссылки

1. Тарьян, Роберт Эндре (1975). «Эффективность хорошего, но не линейного алгоритма объединения множеств». Журнал ACM . 22 (2): 215–225. doi :10.1145/321879.321884. hdl : 1813/5942 . S2CID  11105749.
2. Галлер, Бернард А.; Фишер , Майкл Дж. (май 1964). «Улучшенный алгоритм эквивалентности». Сообщения ACM . 7 (5): 301–303. doi : 10.1145/364099.364331 . S2CID  9034016.. Статья, положившая начало непересекающимся лесам.
3. Хопкрофт, Дж. Э .; Ульман, Дж. Д. (1973). «Алгоритмы слияния множеств». Журнал SIAM по вычислениям . 2 (4): 294–303. doi :10.1137/0202024.
4. Tarjan, Robert E. ; van Leeuwen, Jan (1984). «Анализ алгоритмов объединения множеств в худшем случае». Journal of the ACM . 31 (2): 245–281. doi : 10.1145/62.2160 . S2CID  5363073.
5. Tarjan, Robert Endre (1979). «Класс алгоритмов, требующих нелинейного времени для поддержания непересекающихся множеств». Журнал компьютерных и системных наук . 18 (2): 110–127. doi : 10.1016/0022-0000(79)90042-4 .
6. Фредман, М.; Сакс, М. (май 1989). "Сложность зонда ячейки динамических структур данных". Труды двадцать первого ежегодного симпозиума ACM по теории вычислений - STOC '89 . стр. 345–354. doi : 10.1145/73007.73040 . ISBN 0897913078. S2CID  13470414. Теорема 5: Любая реализация CPROBE(log n ) задачи объединения множеств требует Ω( m α( m , n )) времени для выполнения m операций Find и n −1 операций Union, начиная с n одноэлементных наборов.
7. Галил, З.; Итальяно, Г. (1991). «Структуры данных и алгоритмы для задач объединения непересекающихся множеств». ACM Computing Surveys . 23 (3): 319–344. doi :10.1145/116873.116878. S2CID  207160759.
8. Андерсон, Ричард Дж.; Уолл, Хизер (1994). Параллельные алгоритмы без ожидания для задачи поиска объединения . 23-й симпозиум ACM по теории вычислений. С. 370–380.
9. Коншон, Сильвен; Филлиатр, Жан-Кристоф (октябрь 2007 г.). «Постоянная структура данных Union-Find». Семинар ACM SIGPLAN по ML. Фрайбург, Германия.
10. Гарольд Н. Габов, Роберт Эндре Тарьян, «Линейный алгоритм для специального случая объединения непересекающихся множеств», Журнал компьютерных и системных наук, том 30, выпуск 2, 1985, стр. 209–221, ISSN 0022-0000, https://doi.org/10.1016/0022-0000(85)90014-5
11. Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2009). "Глава 21: Структуры данных для непересекающихся множеств". Введение в алгоритмы (третье изд.). MIT Press. стр. 571–572. ISBN 978-0-262-03384-8.
12. Раймунд Зайдель , Миха Шарир. «Анализ сверху вниз сжатия пути», SIAM J. Comput. 34(3):515–525, 2005
13. Тарьян, Роберт Эндре (1975). «Эффективность хорошего, но не линейного алгоритма объединения множеств». Журнал ACM . 22 (2): 215–225. doi :10.1145/321879.321884. hdl : 1813/5942 . S2CID  11105749.
14. Хопкрофт, Дж. Э.; Ульман, Дж. Д. (1973). «Алгоритмы слияния множеств». Журнал SIAM по вычислениям . 2 (4): 294–303. doi :10.1137/0202024.
15. Роберт Э. Тарьян и Ян ван Леувен . Анализ наихудшего случая алгоритмов объединения множеств. Журнал ACM, 31(2):245–281, 1984.
16. Блум, Норберт (1985). «О временной сложности наихудшего случая для одной операции задачи объединения непересекающихся множеств». 2-й симпозиум. Теоретические аспекты компьютерной науки : 32–38.
17. Alstrup, Stephen; Ben-Amram, Amir M.; Rauhe, Theis (1999). "Оптимальность в худшем случае и амортизированная оптимальность в union-find (Расширенный реферат)". Труды тридцать первого ежегодного симпозиума ACM по теории вычислений . стр. 499–506. doi :10.1145/301250.301383. ISBN 1581130678. S2CID  100111.
18. Альструп, Стивен; Торуп, Миккель; Гёрц, Инге Ли; Рауэ, Тайс; Цвик, Ури (2014). «Найти объединение с удалениями в постоянное время». Транзакции ACM на алгоритмах . 11 (1): 6:1–6:28. дои : 10.1145/2636922. S2CID  12767012.
19. Бен-Амрам, Амир М.; Йоффе, Саймон (2011). «Простой и эффективный алгоритм объединения-поиска-удаления». Теоретическая информатика . 412 (4–5): 487–492. doi :10.1016/j.tcs.2010.11.005.
20. Найт, Кевин (1989). «Унификация: многопрофильное исследование» (PDF) . ACM Computing Surveys . 21 : 93–124. doi :10.1145/62029.62030. S2CID  14619034.

Внешние ссылки

• Реализация C++, часть библиотек Boost C++
• Реализация Java, часть библиотеки JGraphT
• Реализация Javascript
• Реализация Python