Пиксели на цифровой фотографии, компьютеры в сети, люди в социальной сети - все это связанные объекты.
Учитывая набор из N объектов, соедините два объекта или спросите, связаны ли два объекта (напрямую или напрямую).
Проблема в том, чтобы иметь возможность реализовать две команды; объединение и соединение.
union(2, 5) // connect object 2 with object 5 connected(1 , 6) // is object 1 connected to object 6?
Свойства подключения
Мы предполагаем, что «связан с» является отношением эквивалентности . Отношение эквивалентности разделяет объекты на классы эквивалентности или связанные компоненты.
- Возвратное → p связано с p.
- Симметричный → Если p соединен с q, то q соединен с p.
- Транзитивный → Если p связан с q, а q связан с r, то p связан с r.
Осуществление операций
- Найти: в каком компоненте находится объект p?
- Связано: находятся ли объекты p и q в одном компоненте?
- Объединение: соедините два компонента, содержащие объекты p и q (если это еще не сделано).
Связанные компоненты - это подмножества, каждое из которых состоит из связанных объектов.
Тип данных Union-Find
Цель состоит в том, чтобы спроектировать эффективную структуру данных для типа данных, называемого union – find (также известного как непересекающиеся множества), с помощью двух команд; союз и связаны.
Это может быть реализовано несколькими разными алгоритмами. Мы собираемся изучить два алгоритма; Быстрый поиск и Быстрое объединение.
Быстрый поиск
Это алгоритм решения проблемы динамического подключения, также называемый «энергичным подходом».
Инициализировать
Каждый объект в массиве имеет значение или идентификатор, и изначально идентификатор является его индексом. Элемент p связан с элементом q, если у них одинаковый идентификатор.
for (int i = 0; i < n; i++)
id[i] = i; // set id of the object at index i
Союз
При соединении двух объектов p и q измените идентификатор всех объектов, имеющих идентификатор p, на идентификатор q, или наоборот. Итак, нам нужно будет выполнить цикл по всем элементам массива, чтобы проверить идентификатор каждого.
if (pID == qID) return; // already connected?
for (int i = 0; i < id.length; i++)
if (id[i] == pID)
id[i] = qID;
Подключено
Два объекта связаны тогда и только тогда, когда у них одинаковый идентификатор.
return id[p] == id[q];
Анализируя
Он быстро проверяет наличие соединения, медленно создает массив объектов и соединяет объекты.
- Инициализировать и объединить → O (N)
- Подключено → O (1)
Быстрый союз
Это алгоритм решения проблемы динамического подключения, также называемый «ленивым подходом».
Инициализировать
Массив представляет родительский элемент каждого объекта. Изначально родителем объекта является сам объект; каждый объект является корнем.
Теперь мы можем представить, что структура данных состоит из деревьев, каждое дерево имеет связанные объекты, и деревья могут не быть связаны друг с другом.
for (int i = 0; i < n; i++)
parent[i] = i; // set parent of the object at index i
Корень
Получить корень объекта. Это просто вспомогательный метод, который будет использоваться в командах union и connected.
while (p != parent[p])
p = parent[p];
return p;
Союз
При соединении двух предметов p и q соедините корни. Итак, измените родительский элемент корня p на корень q или наоборот. Теперь корень p стал потомком корня q (как если бы мы соединяли два дерева или подмножества).
int rootP = root(p); int rootQ = root(q); if (rootP == rootQ) return; // already connected? parent[rootP] = rootQ;
Связаны
Два объекта связаны, если их корень одинаковый. Итак, мы должны проверить родителей каждого объекта до корня.
return root(p) == root(q);
Анализируя
Он медленно проверяет наличие соединения, медленно создает массив объектов и соединяет объекты. Соединение двух объектов может занять O (N), когда глубина дерева равна N.
- Инициализировать и объединить и подключить → O (N).
Улучшения Quick Union
1. Взвешенный быстрый союз
Избегайте высоких деревьев, отслеживая количество объектов в каждом дереве, и поэтому мы можем поддерживать баланс, связывая корень меньшего (или более короткого) дерева с корнем большего (или более высокого) дерева.
Мы добавим дополнительный массив, обозначающий размер (или глубину) поддерева, сформированного каждым узлом.
// union by size (initially size[i] = 1)
if (size[rootP] < size[rootQ]) {
parent[rootP] = rootQ;
size[rootQ] += size[rootP];
} else {
parent[rootQ] = rootP;
size[rootP] += size[rootQ];
}
// union by depth (initially depth[i] = 0)
if (depth[rootP] < depth[rootQ])
parent[rootP] = rootQ;
else if (depth[rootP] > depth[rootQ])
parent[rootQ] = rootP;
else {
parent[rootQ] = rootP;
depth[rootP]++;
}
Анализируя
Время, затрачиваемое на объединение и связанные команды, не превышает глубины самого высокого дерева, которое составляет не более O (LogN).
Доказательство: когда T1 объединяется с T2, где T1 ≤T2, глубина T1 увеличивается на 1. Теперь глубина T2 (после объединения) увеличится на 1, если объединить с T3, где Т3 ≥ Т2. Итак, каждый раз нам нужно дерево X ≥ tree Y, чтобы увеличить глубину дерева Y на 1. Следовательно, размер T1 может увеличиваться не более чем на LogN.
- Union & Connected → O (Вход в систему)
2. Сжатие пути
Расправьте дерево; Всякий раз, когда вы хотите перейти к корню от объекта, назначьте родительский элемент текущего объекта его прародителю (или корню). Это правило применяется до самого дерева.
Это уменьшит количество шагов, необходимых для перехода к корневому объекту от текущего объекта.
// path compression by linking to the root
int root = p;
while (root != parent[root])
root = parent[root];
while (p != root) {
int newp = parent[p];
parent[p] = root;
p = newp;
}
// path compression by linking to grandparent(halving the depth)
while (p != parent[p]) {
parent[p] = parent[parent[p]];
p = parent[p];
}
Анализируя
Амортизированная стоимость одной операции, как известно, является логарифмической.
- Union & Connected → O (LogN) (амортизируется)
Резюме
- Быстрый поиск → O (1) для связного и O (N) для объединения.
- Быстрое соединение → O (N).
- Взвешенное быстрое объединение → O (LogN).
- Quick Union и Path Compression → O (LogN) (амортизировано).
- Взвешенное быстрое объединение со сжатием пути → O (Log * N) (амортизировано).
Log * N - повторный логарифм N, обычно читается как «логарифм».
Другие связанные проблемы (просачивание)
Структура данных под названием union-find, которую мы использовали для решения проблемы динамического соединения, также может использоваться для решения других проблем, таких как перколяция.
Задача перколяции задается сеткой из N x N элементов, окрашенных в белый цвет, если он открыт, синий, если он соединен с любым элементом в верхнем ряду, и черный, если он закрыт. Система просачивается? Другими словами, соединяется ли верхний ряд с нижним через открытые элементы ?.
Проблема просачивания проявляется в электричестве, потоке жидкости, социальных взаимодействиях и многом другом.
С сеткой из N x N элементов, чтобы проверить, связан ли какой-либо элемент в первой строке с каким-либо элементом внизу. Для этого потребуется N² вызовов команды connected.
Уловка, которую мы можем использовать, состоит в том, чтобы соединить все элементы в первой строке с «виртуальным» элементом, и мы сделаем то же самое для всех элементов в нижней строке.
Теперь, чтобы узнать, просачивается ли система, мы проверяем, подключен ли виртуальный элемент вверху к элементу внизу. Таким образом, это более эффективный алгоритм, поскольку для него требуется только один вызов команды connected.
Остерегайтесь этой ошибки!
Если элементы в нижнем ряду соединены с «виртуальным» нижним элементом, а элемент A внизу соединяется с верхним виртуальным узлом (стал синим).
Теперь, когда открывается другой элемент B в нижнем ряду, он также будет окрашен в синий цвет. Почему? Поскольку он также подключен к элементу A (через виртуальный нижний элемент), который, в свою очередь, подключен к верхнему виртуальному узлу.
Решения
Либо используйте две сетки N x N, где первая имеет только виртуальный верхний элемент и используется как основная сетка (представляет систему), а вторая имеет как верхние, так и нижние виртуальные элементы, и он просто используется, чтобы определить, просачивается ли система или нет.
Или, используйте одну сетку только с верхним виртуальным элементом, и всякий раз, когда мы открываем элемент в последней строке, и он связан с любым узлом наверху, помечайте систему как перколятор.
