Эта статья включена в репозиторий Github.GitHub.com/silently952…
Плагины IDEA, обычно используемые программистами:GitHub.com/silently952…
Полностью открытый проект Taoke:GitHub.com/silently952…
Публичный аккаунт WeChat: бета изучает Java
предисловие
Я уехал в свой родной город во время праздника Весны и перестал обновляться на много дней.Это первая статья, которая вышла за ночь после Нового года.Давайте поговорим о том, что произошло во время праздника Весны.В этот раз я пошла домой и встретила богиня моих студенческих дней, на мой взгляд, это
«Из грязи, но не в пятнах, чистый, но не демонический»
Я не ожидал, что поеду домой, встретил ее, жирное тело, и глаза образа богини мгновенно разбились, прямо как Леонардо да Винчи Мона Лиза снова встретился
«Ханьли благовония продаются зелеными листьями»
ну давайте вернемся к делу.
Иногда нам нужно решить, соединены ли два компьютера в большую сеть и нужно ли установить новое соединение для общения, или являются ли два человека друзьями в социальной сети (подключение означает дружбу). В этом приложении нам может понадобиться иметь дело с миллионами объектов и сотнями миллионов соединений, как мы можем быстро определить, связаны ли они? Это требует использования алгоритма объединения-поиска
концепция
связанный
Если ввести пару целых чисел, где каждое число представляет какой-то объект (человека, адрес или компьютер и т. д.), то целочисленная пара p, q понимается как «p соединен с q», а соединение имеет следующий вид характеристики:
- Рефлексивность: p связано с p
- Симметрия: если p соединен с q, то q соединен с p.
- Транзитивность: если p соединен с q, а q связан с r, то p также связан с r.
Как объекты связаны с числами, об алгоритмической таблице символов мы поговорим позже
Класс эквивалентности
Если предположить, что связь является отношением эквивалентности, то отношение эквивалентности может разделить объекты на несколько классов эквивалентности.В этом алгоритме два объекта принадлежат одному и тому же классу эквивалентности тогда и только тогда, когда они связаны.
контакт
Какой-то объект во всей сети называется контактом
подключенные компоненты
Целочисленные пары называются соединениями, а классы эквивалентности называются компонентами связности или просто компонентами.
динамическое подключение
Цель алгоритма объединения-поиска состоит в том, что когда программа считывает пару целых чисел pq из входных данных, если все известные пары целых чисел не могут показать, что pq связно, то выводит пару целых чисел, в противном случае игнорирует пару целых чисел; мы необходимо разработать структуру данных для хранения информации обо всех известных парах целых чисел и определить, связаны ли входные пары целых чисел.Эта проблема называется проблемой динамической связности.
Определение API алгоритма объединения
public interface UF {
void union(int p, int q); //在p与q之间添加一条连接
int find(int p); //返回p所在分量的标识符
boolean connected(int p, int q); //判断出p与q是否存在于同一个分量中
int count(); //统计出连通分量的数量
}
Если два контакта находятся в разных компонентах, операция объединения объединит два компонента. В начале у нас есть N компонентов (по одному на каждый контакт), и количество уменьшается на единицу после объединения двух компонентов.
Абстрактная реализация выглядит следующим образом:
public abstract class AbstractUF implements UF {
protected int[] id;
protected int count;
public AbstractUF(int N) {
count = N;
id = new int[N];
for (int i = 0; i < N; i++) {
id[i] = i;
}
}
@Override
public boolean connected(int p, int q) {
return find(p) == find(q);
}
@Override
public int count() {
return count;
}
}
Далее мы в основном обсудим, как реализовать метод объединения и метод поиска.
алгоритм быстрого поиска
Идея этого алгоритма заключается в том, что все контакты в одном подключенном компоненте имеют одинаковое значение в id[], и способ определить, подключено ли соединение, состоит в том, чтобы определить, равен ли id[p] id[q ].
public class QuickFindImpl extends AbstractUF {
public QuickFindImpl(int N) {
super(N);
}
@Override
public int find(int p) {
return id[p];
}
@Override
public void union(int p, int q) {
int pId = find(p);
int qId = find(q);
if (pId == qId) { //如果相等表示p与q已经属于同一分量中
return;
}
for (int i = 0; i < id.length; i++) {
if (id[i] == pId) {
id[i] = qId; //把分量中所有的值都统一成qId
}
}
count--; //连通分量数减一
}
}
- Анализ алгоритмов:
Очевидно, что операция find() выполняется очень быстро, а временная сложность составляет O(1), но алгоритм объединения не может обрабатывать большие данные, поскольку каждый раз требуется весь массив переменных, поэтому временная сложность метода объединения составляет O(1). н)
Быстросоразмерный алгоритм
Чтобы улучшить скорость метода UNION, нам нужно рассмотреть другой алгоритм, использовать ту же структуру данных, просто переопределив значение ID[], а значение ID[], соответствующее каждому контакту, будет другим в том же компоненте. Имя контакта
После инициализации массива ссылка каждого узла указывает сама на себя; массив id[] использует父链接в виде森林, каждая операция объединения найдет根节点Объединить.
public class QuickUnionImpl extends AbstractUF {
public QuickUnionImpl(int N) {
super(N);
}
@Override
public int find(int p) {
//找出p所在分量的根触点
while (p != id[p]) {
p = id[p];
}
return p;
}
@Override
public void union(int p, int q) {
int pRoot = find(p); //找出q p的根触点
int qRoot = find(q);
if (pRoot == qRoot) { //处于同一分量不做处理
return;
}
id[pRoot] = qRoot; //根节点
count--;
}
}
- Анализ алгоритмов:
Похоже, что алгоритм быстрого объединения работает быстрее, чем алгоритм быстрого поиска, потому что объединению не нужно проходить весь массив для каждой пары входных данных. В лучшем случае методу find требуется только один раз получить доступ к массиву, чтобы получить корневой контакт, тогда временная сложность метода объединения составляет O (n); Рассмотрим наихудший входной случай, как показано ниже:
Метод find должен получить доступ к массиву n-1 раз, поэтому временная сложность метода объединения составляет O (n²).
Алгоритм взвешенного быстрого объединения
Чтобы гарантировать, что наихудший случай алгоритма быстрого объединения не произойдет, мне нужно записать размер каждого дерева и всегда соединять маленькое дерево с большим деревом при выполнении операции слияния компонентов. построенное по этому алгоритму, будет намного меньше высоты дерева, построенного по невзвешенной версии.
public class WeightedQuickUnionImpl extends AbstractUF {
private int[] sz;
public WeightedQuickUnionImpl(int N) {
super(N);
sz = new int[N];
for (int i = 0; i < N; i++) {
sz[i] = 1;
}
}
@Override
public void union(int p, int q) {
int pRoot = find(p); //找出q p的根触点
int qRoot = find(q);
if (pRoot == qRoot) { //处于同一分量不做处理
return;
}
//小树合并到大树
if (sz[pRoot] < sz[qRoot]) {
sz[qRoot] += sz[pRoot];
id[pRoot] = qRoot;
} else {
sz[pRoot] += sz[qRoot];
id[qRoot] = pRoot;
}
count--;
}
@Override
public int find(int p) {
//找出p所在分量的根触点
while (p != id[p]) {
p = id[p];
}
return p;
}
}
- Анализ алгоритмов:
В худшем случае каждое дерево, объединенное объединением, имеет одинаковый размер, все они содержат 2 в n-й степени узлов, высота равна n, а высота после слияния становится n+1, что можно получить. метода объединения O(lgN)
Суммировать
Алгоритм поиска профсоюза может определить, только связаны ли данные два целых числа и не могут дать конкретный путь; позже мы говорили о алгоритме графа, который может дать конкретный путь
| алгоритм | union() | find() |
|---|---|---|
| алгоритм быстрого поиска | N | 1 |
| алгоритм быстрого объединения | высота дерева | высота дерева |
| Алгоритм взвешенного быстрого объединения | lgN | lgN |
Наконец (обратите внимание, не потеряйтесь)
В тексте может быть больше или меньше недостатков и ошибок.Если у вас есть предложения или мнения, вы можете их комментировать и обмениваться.
Наконец,Писать не легко, пожалуйста, не проституируй меня., я надеюсь, что мои друзья могутНравится Комментарий ПодписатьсяСанлян, потому что это все источники мотивации, которыми я могу поделиться🙏
Весь исходный код этой статьи помещен в репозиторий github.GitHub.com/silently952…
Справочник: алгоритмы, четвертое издание