Union-Find: быстрый поиск
В этом разделе представлены базовые операции на основе структуры непересекающихся множеств из предыдущего раздела: запрос, объединение и определение того, связаны ли элементы.
Запросить ID множества элемента и вернуть его напрямую.idзначение массива,O(1)временная сложность.
...
private int find(int p) {
assert p >= 0 && p < count;
return id[p];
}
...
private int find(int p) {
assert p >= 0 && p < count;
return id[p];
}
...
Объединить множества, к которым принадлежат элементыpи элементq. Процесс объединения требует обхода всех элементов, затем объединения ID множеств двух элементов. Этот процесс имеет...O(n)сложность.
...
public void unionElements(int p, int q) {
int pID = find(p);
int qID = find(q);
if (pID == qID)
return;
for (int i = 0; i < count; i++)
if (id[i] == pID)
id[i] = qID;
}
...
public void unionElements(int p, int q) {
int pID = find(p);
int qID = find(q);
if (pID == qID)
return;
for (int i = 0; i < count; i++)
if (id[i] == pID)
id[i] = qID;
}
...
Пример кода на Java
Исходный пакет:Скачать
код файла UnionFind1.java:
package example.union;
/**
* Первая версия union-Find
*/
public class UnionFind1 {
// Наша первая версия Union-Find по сути представляет собой массив
private int[] id;
// количество элементов данных
private int count;
public UnionFind1(int n) {
count = n;
id = new int[n];
// Инициализация: каждый id[i] указывает на самого себя, нет объединённых элементов
for (int i = 0; i < n; i++)
id[i] = i;
}
// процесс find, найти номер множества, соответствующего элементу p
private int find(int p) {
assert p >= 0 && p < count;
return id[p];
}
// проверить, принадлежат ли элемент p и элемент q одному и тому же множеству
// Сложность O(1)
public boolean isConnected(int p, int q) {
return find(p) == find(q);
}
// объединить множества, содержащие элемент p и элемент q
// Сложность O(n)
public void unionElements(int p, int q) {
int pID = find(p);
int qID = find(q);
if (pID == qID)
return;
// Процесс объединения требует однократного обхода всех элементов и объединения ID множеств двух элементов
for (int i = 0; i < count; i++)
if (id[i] == pID)
id[i] = qID;
}
}
/**
* Первая версия union-Find
*/
public class UnionFind1 {
// Наша первая версия Union-Find по сути представляет собой массив
private int[] id;
// количество элементов данных
private int count;
public UnionFind1(int n) {
count = n;
id = new int[n];
// Инициализация: каждый id[i] указывает на самого себя, нет объединённых элементов
for (int i = 0; i < n; i++)
id[i] = i;
}
// процесс find, найти номер множества, соответствующего элементу p
private int find(int p) {
assert p >= 0 && p < count;
return id[p];
}
// проверить, принадлежат ли элемент p и элемент q одному и тому же множеству
// Сложность O(1)
public boolean isConnected(int p, int q) {
return find(p) == find(q);
}
// объединить множества, содержащие элемент p и элемент q
// Сложность O(n)
public void unionElements(int p, int q) {
int pID = find(p);
int qID = find(q);
if (pID == qID)
return;
// Процесс объединения требует однократного обхода всех элементов и объединения ID множеств двух элементов
for (int i = 0; i < count; i++)
if (id[i] == pID)
id[i] = qID;
}
}