Во -первых, давайте посмотрим на два картинки сжатия пути:
Наборы Union-Find-очень деликатная и практическая структура данных, которая в основном используется для решения проблемы слияния некоторых неинтересованных наборов. Некоторые распространенные применения включают соединение подграфов, алгоритмы Крускала для поиска минимального дерева охраны и наименее общих предков (LCA).
При использовании и поиске набора сначала будет набор непересекающихся динамических наборов s = {s 1, s 2, ⋯, s k}, в котором обычно используется целое число для представления элемента в наборе.
Каждый набор может содержать один или несколько элементов, а элемент в наборе выбирается в качестве представителя. Не важно заботиться о том, какие элементы содержатся в каждом наборе, и не важно заботиться о том, какой элемент выбирается в качестве представителя. Что нас волнует, так это то, что для данного элемента мы можем быстро найти набор (представление), где находится этот элемент, и объединить наборы, где расположены два элемента, и временная сложность этих операций постоянна.
Есть три основные операции для проверки и сбора:
MAKETET (S): Создайте новый набор поиска, который содержит S одноэлементные наборы.
Uniionset (x, y): объединяет наборы, где расположены элемент x и элемент Y, и требует, чтобы наборы, где расположены x и y, не пересекались, и если они пересекаются, они не сливаются.
Найдите (x): Найдите представителя набора, где находится элемент X. Эта операция также может быть использована для определения того, находятся ли два элемента в одном и том же наборе. Просто сравните их соответствующих представителей.
пакет com.datastructure.union_find; // Наше пятое издание Union-Findpublic Class UnionFind5 {// Rank [i] представляет количество слоев дерева, представленного набор глубина. Это просто стандарт для сравнения частного ранга; частный int [] родитель; // родитель [i] представляет родительский узел, на который указывает I-Th Element Private Count; // количество данных // Constructor Public UnionFind5 (int count) {rank = new int [count]; родитель = новый int [count]; this.count = count; // инициализация, каждый родитель [i] указывает на себя, указывая, что каждый элемент формирует свой собственный набор для (int i = 0; i <count; i ++) {parent [i] = i; ранг [i] = 1; }} // Процесс поиска, найдите установленное число, соответствующее элементу p // o (h) сложности, h - высота дерева private int sind (int p) {assert (p> = 0 && p <count); // Сжатие пути 1 while (p! = parent [p]) {parent [p] = родитель [parent [p]]; p = родитель [P]; } return p; // Сжатие пути 2, рекурсивный алгоритм // if (p! = parent [p]) // parent [p] = find (parent [p]); // return parent [p]; } // Проверьте, принадлежат ли элемент P и элемент Q сложности // o (h), h - высота дерева, общедоступного логического, искаженного (int p, int q) {return find (p) == find (q); } // слияние набора, к которому элемент p и элемент q принадлежит // o (h) сложности, h - высота дерева Public void UnionElements (int p, int q) {int proot = find (p); int qroot = find (q); if (proot == QROOT) return; // Судить направление слияния на основе различного количества элементов в дереве, где расположены два элемента // слияние сет с меньшим количеством элементов на набор с большим количеством элементов, если (rank [proot] <rank [qRoot]) {parent [proot] = qRoot; } else if (rank [qRoot] <rank [proot]) {parent [qroot] = proot; } else {// rank [proot] == rank [qRoot] parent [proot] = qRoot; ранг [qRoot] += 1; // В настоящее время я поддерживаю значение ранга}}}Суммировать
Выше приведено все подробное объяснение кода сжатия пути в этой статье о реализации и сборе программирования Java. Я надеюсь, что это будет полезно для всех. Заинтересованные друзья могут продолжать ссылаться на другие связанные темы на этом сайте. Если есть какие -либо недостатки, пожалуйста, оставьте сообщение, чтобы указать это. Спасибо, друзья, за вашу поддержку на этом сайте!