Задача

Структура данных Union-Find обеспечивает хранение информации о непересека- ющихся множествах (например, компонентах графа) в следующем смысле. Для заданного узла и операция Find(u) возвращает имя множества, содержащего u.
При помощи этой операции можно проверить, принадлежат ли два узла и и v к одному множеству, просто проверяя условие Find(u) = Find(v). Структура данных также реализует операцию Uniоn(А, B), которая берет два множества A и B и сливает их в одно множество.

Эти операции могут использоваться для хранения информации о компонентах эволюционирующего графа G = (V, E) по мере добавления новых ребер. Множества представляют компоненты связности графа. Для узла и операция Find(u) возвраща- ет имя компоненты, содержащей u. Чтобы добавить в граф ребро (u, v), мы сначала проверяем, принадлежат ли и и v одной компоненте связности (условие Find(u) = Find(v)). Если они не принадлежат одной компоненте, то операция Union(Find(u), Find(v)) используется для слияния двух компонент. Важно заметить, что структура Union-Find может использоваться только для управления компонентами графа при добавлении ребер: она не предназначена для обработки удаления ребер, которое может привести к «разделению» одной компоненты надвое.

Итак, структура Union-Find будет поддерживать три операции.

♦ MakeUnionFind(S) для множества S возвращает структуру Union-Find. Например, эта структура соответствует набору компонент связности графа без ребер. Мы постараемся реализовать MakeUnionFind за время O(n), где n = | S |.

♦ Для элемента и Sоперация Find(u) возвращает имя множества, содержащего u. Нашей целью будет реализация Find(u) за время О(log n). Некоторые реализа- ции, которые будут упомянуты в тексте, позволяют выполнить эту операцию за время О(1).

♦ Для двух множеств А и B операция Union(А, B) изменяет структуру данных, объ- единяя множестваA и B в одно. Нашей целью будет реализация Union за время O(log n).

Стоит разобраться, что же подразумевается под именем множества — напри- мер, возвращаемого операцией Find. Имена множеств определяются достаточно гибко; они просто должны быть непротиворечивыми в том отношении, что Find(v) и Find(w) должны возвращать одно имя, если v и w принадлежат одному множеству, и разные имена в противном случае. В наших реализациях имя каждого множества будет определяться одним из содержащихся в нем элементов.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Задача:

  1. ЗАДАЧИ ОБЩИЕ И ЗАДАЧИ СПЕЦИАЛЬНЫЕ
  2. 7. Каждый школьник – это сложнейший мир проблем и задач. Забота о своевременном решении этих проблем и задач составляет основу строительства новой школы
  3. Вторая зрелость наступает тогда, когда человек выполнил задачи зрелого человека, осознал задачи второй зрелости и готов их выполнять
  4. ЗАДАЧА
  5. ЗАДАЧА: РЕШЕНИЕ
  6. Основные задачи.
  7. в) Задачи
  8. в) Задачи
  9. ПСИХОАНАЛИЗ: ЗАДАЧА
  10. ЗАДАЧА ДВИГАТЕЛЬНАЯ
  11. Основные задачи
  12. Правило решаемой психологической задачи.