Структура данных поиска в Union

Ответ 1

Это довольно поздний ответ, но это, вероятно, не ответили в другом месте в stackoverflow, и поскольку это самая большая страница для кого-то, ищущего union-find, вот подробное решение.

Find-Union - очень быстрая операция, выполняющая почти постоянное время. Это следует за идеями Джереми о сжатии пути и размерах отслеживания. Сжатие пути выполняется для каждой операции поиска, тем самым принимая амортизированное время lg * (n). lg * подобна обратной функции Аккермана, растущей настолько очень медленно, что она редко превышает 5 (по крайней мере, до n < 2 ^ 65535). Множества Union/Merge выполняются ленивыми, просто указывая 1 корень на другой, в частности, меньший корень набора для большего корня набора, который завершается в постоянное время.

Обратитесь к приведенному ниже коду из https://github.com/kartikkukreja/blog-codes/blob/master/src/Union%20Find%20%28Disjoint%20Set%29%20Data%20Structure.cpp

class UF {
  int *id, cnt, *sz;
  public:
// Create an empty union find data structure with N isolated sets.
UF(int N) {
    cnt = N; id = new int[N]; sz = new int[N];
    for (int i = 0; i<N; i++)  id[i] = i, sz[i] = 1; }
~UF() { delete[] id; delete[] sz; }

// Return the id of component corresponding to object p.
int find(int p) {
    int root = p;
    while (root != id[root])    root = id[root];
    while (p != root) { int newp = id[p]; id[p] = root; p = newp; }
    return root;
}
// Replace sets containing x and y with their union.
void merge(int x, int y) {
    int i = find(x); int j = find(y); if (i == j) return;
    // make smaller root point to larger one
    if (sz[i] < sz[j]) { id[i] = j, sz[j] += sz[i]; }
    else { id[j] = i, sz[i] += sz[j]; }
    cnt--;
}
// Are objects x and y in the same set?
bool connected(int x, int y) { return find(x) == find(y); }
// Return the number of disjoint sets.
int count() { return cnt; }
};

Добровольное голосование или принятие, если хотите.

Ответ 2

Структура данных может быть представлена ​​как дерево, а ветки обращены (вместо того, чтобы указывать вниз, ветки указывают вверх на родителя --- и связывают ребенка с его родителем).

Если я правильно помню, это можно показать (легко):

• это сжатие пути (всякий раз, когда вы выполняете поиск "родительского" набора A, вы "сжимаете" путь, чтобы каждый последующий вызов для них обеспечивал родителя во времени O (1)) привести к сложности O (log n) для каждого вызова;

• который балансирует (вы отслеживаете количество детей, у каждого из которых есть набор, и когда вам нужно "объединить" два набора, вы делаете одно с меньшим количеством дочернего ребенка одного из них) приводит к сложности O (log n) для каждого вызова.

Более активное доказательство может показать, что при объединении обеих оптимизаций вы получаете среднюю сложность, которая является обратной функцией Аккермана, написанной α (n), и это было основным изобретением Тарьяна для этой структуры.

Позже было показано, что для некоторых конкретных шаблонов использования эта сложность на самом деле постоянна (хотя для всех практических целей обратное действие аккермана составляет около 4). Согласно странице Википедии о Union-Find, в 1989 году амортизированная стоимость одной операции любой эквивалентной структуры данных была показана как Ω (α (n)), доказывая, что текущая реализация асимптотически оптимальна.

Ответ 3

Собственная структура данных объединения-поиска использует сжатие путей во время каждой находки. Это амортизирует затраты, и каждая операция пропорциональна обратной функции Аккермана, которая в основном делает ее постоянной (но не совсем).

Если вы реализуете его с нуля, я бы предложил использовать древовидный подход.

Ответ 4

Простая структура union-set хранит массив (element → set), делая поиск, который устанавливает постоянное время; их обновление амортизируется log n time, а конкатенация списков постоянна. Не так быстро, как некоторые из вышеперечисленных подходов, но тривиальны для программы и более чем достаточно хороши, чтобы улучшить время работы Big-O, скажем, алгоритма минимального алгоритма Kruskal Mining Spanning Tree.