Описание тега union-find
Структура данных объединения / поиска - это структура данных, используемая для поддержки раздела набора.
4
ответа
Объединение найти структуру данных
Для многих проблем, которые я вижу, рекомендуется использовать структуру данных union-find. Я пытался прочитать об этом и подумать, как это реализовано (с использованием C++). В настоящее время я понимаю, что это не что иное, как список наборов. Ита…
28 ноя '11 в 17:55
0
ответов
Проверить правильность ввода двоичного дерева (используя union-find)
Учитывая несколько кортежей в форме (A,B), где A - родительский элемент, а B - дочерний элемент в двоичном дереве, найдите, допустим ли ввод или нет. Были предоставлены 4 условия ошибки: Если у родителя более 2 детей, Если введены повторяющиеся корт…
01 сен '15 в 15:40
1
ответ
Union-Find операции на дереве?
Может кто-нибудь, пожалуйста, объясните ответ жирным шрифтом? Как это сделано? Ниже приведена последовательность из четырех операций Union-Find (с взвешенным объединением и полным сжатием), которые привели к следующему восходящему дереву. Какие были…
11 июн '16 в 03:29
0
ответов
Есть ли способ эффективно обновить ранж в "Взвешенном объединении-поиске со сжатием пути" до его реального значения?
После сжатия пути ранг корня может быть меньше, но не обновляется. Тогда вы можете связать действительно большее дерево с меньшим. Есть ли эффективный способ обновить ранг корня до реальной стоимости?
25 окт '18 в 04:39
2
ответа
В поисках правильного объединения DST с обратно-аккерманной сложностью
Я говорю о структуре данных union-find-disjoint. В Интернете есть множество ресурсов о том, как это реализовать. До сих пор я узнал о двух методах оптимизации для профсоюзов. Первый - это "балансировка" дерева с помощью переменной Rank, которая гово…
12 апр '15 в 02:13
1
ответ
Как использовать union-find, minheap, Kruskal's и алгоритм сортировки для создания связующего дерева с минимальной стоимостью? (C++)
Я прошу прощения, если этот вопрос является немного широким, но я испытываю затруднения, пытаясь понять, как я создал бы остовное дерево минимальной стоимости. Это в C++, если это вообще имеет значение. Из того, что я понимаю, вы бы использовали Kru…
06 фев '11 в 21:30
1
ответ
Анализируем Временную сложность алгоритма поиска объединения?
Пожалуйста, дайте краткий и простой подход к анализу временной сложности алгоритма union-find. В двух случаях 1. Стандартный подход 2. Эвристический подход с взвешенным объединением Я знаю, что в стандартной версии его временная сложность: O (n ^ 2)…
06 дек '13 в 09:38
1
ответ
Как избежать IORefs в чистом коде
Я заметил, что Data.UnionFind использует монаду IO для предоставления указателей через IORefs. Я думаю, что все радостно звонят unsafePerformIO при локальном использовании в чистом коде, так как структура данных так хорошо понятна, но.. Есть ли кано…
24 апр '12 в 13:18
2
ответа
Взвешенное быстрое объединение с алгоритмом сжатия пути: анализ временной сложности
Я изучаю алгоритм взвешенного быстрого объединения со сжатием пути для структуры объединения / поиска. Сайт edu в Принстоне подробно объяснил алгоритм. А вот реализация в Java: public class WQUPC { private int[] id; private int[] sz; public WQUPC(in…
02 сен '16 в 12:43
1
ответ
Возникли проблемы с взвешенными и невзвешенными быстрыми профсоюзными находками
TLDR внизу В школе мне поручили проект программирования по созданию модели перколяции, и я столкнулся с проблемой, которая привела меня в замешательство. Во-первых, мы должны были построить API для запуска перколяционного моделирования. public class…
22 апр '15 в 03:26
0
ответов
Существует ли система БД, которая поддерживает структуру данных Union-Find (Disjoint Sets)
В основном ищет БД, которая поддерживает эту структуру данных OOTB
18 мар '18 в 11:18
0
ответов
Структура данных Union-find - Как использовать make_sets и правильно найти
По сути, я пытаюсь изменить алгоритм Крускала, добавив еще одно условие, помимо проверки, находятся ли вершины u и v в одном и том же компоненте. Я смутно понимаю, как работает структура данных union-find, поэтому я хотел проверить, правильно ли я п…
15 авг '15 в 16:24
0
ответов
Eclipse Java WeightedQuickUnionUF
В данный момент работаю в Eclipse над проблемой. Структура данных weightedQuickUnionFind Что я имею: -список данных в отдельном файле.txt, который содержит идентификаторы пользователей. пример: 0 5 0 2 1 3 1 2 2 5 3 7 В основном это говорит о том, ч…
21 янв '15 в 08:28
1
ответ
Производительность метода поиска объединения, итеративный или рекурсивный
По сути, проблема в том, что я обнаружил, что рекурсивная версия метода union-find быстрее, чем итерационная версия. // the union find method - recursive int find(int k) { if(f[k] != k) f[k] = find(f[k]); return f[k]; } // the union find method - it…
21 ноя '17 в 04:47
0
ответов
В операции объединения, которая лучше на основе ранга или размера, где операция поиска выполняется с использованием сжатия пути
Согласно моему пониманию, объединение по размеру лучше, потому что сжатие пути в операции поиска также изменяет ранг, который не обновляется, тогда как размер остается тем же. Но в некоторых редакционных статьях для задач было выполнено объединение …
28 ноя '17 в 16:08
0
ответов
После использования unionFind я получаю кластер с узлом 10k (NEO4J)
Я использовал unionFind algo, чтобы разделить мой график на кластеры. Я получаю много кластеров, но один из них выглядит странно, так как он имеет 10 тыс. Узлов (у меня 40 тыс. Узлов)!! У кого-нибудь есть объяснение по этому поводу? Я также слышал о…
05 дек '18 в 15:49
3
ответа
Установить алгоритм объединения, используя вектор в C++
Я только использую std::vector в этой задаче, и я могу гарантировать отсутствие дубликатов в каждом векторе (но нет порядка в каждом векторе). Как объединить векторы, которые у меня есть? Пример: Если у меня есть следующие векторы... 1 1 3 2 5 5 4 2…
10 апр '13 в 04:18
1
ответ
Классы эквивалентности и объединения / поиска на функциональном языке
Для алгоритма автоматов мне нужна быстрая структура данных Union-Find на функциональном языке. Поскольку мне нужно формально доказать правильность структуры данных, я бы предпочел простую структуру. Я пытаюсь вычислить классы эквивалентности элемент…
28 мар '13 в 20:39
2
ответа
Посчитайте, сколько разных векторов осталось после объединения
В этой задаче я использую только std::vector, и каждый вектор упорядочен без дубликатов. Теперь я хочу объединить векторы с одинаковыми номерами. Таким образом, 2 3 может быть объединением с 3 4 5, но не с 4 5 или 1 5. Пример: Если у меня есть следу…
10 апр '13 в 22:26
1
ответ
C++ free(): неверная ошибка указателя при сжатии пути (объединение по рангу)
Я просмотрел другие подобные вопросы, но не смог выяснить причину этой ошибки. Я пишу программу на C++ для реализации алгоритма Kruskal Minimum Spanning Tree с использованием объединения по рангу со сжатием пути. Он печатает края MST правильно, но в…
14 апр '16 в 07:29