Union-Find: Объединяй и властвуй

Цели урока

• Понять задачу динамической связности
• Реализовать наивный Union-Find
• Оптимизировать с path compression и union by rank
• Узнать применения в реальных задачах

Предварительные знания

• Графы

• Введение в графы

В социальной сети миллиард пользователей. Как за микросекунду узнать, связаны ли два человека через цепочку друзей? BFS будет работать вечность. Union-Find - мгновенно!

• Facebook - люди, которых вы можете знать
• Kruskal's MST - построение минимального остовного дерева
• Image segmentation - объединение пикселей
• Network connectivity - проверка связности сети

Галлер, Фишер и почти константная оценка Тарьяна

Бернард Галлер и Майкл Фишер описали структуру непересекающихся множеств в 1964 году, когда работали над алгоритмом классов эквивалентности для компилятора Algol в Мичиганском университете. Структура была простой, но её настоящая стоимость оставалась неясной больше десяти лет. В 1975 году Роберт Тарьян проанализировал комбинацию path compression и union by rank и доказал, что последовательность из m операций выполняется за O(m α(n)), где α это обратная функция Аккермана. Эта функция растёт настолько медленно, что не превышает 5 для любого входа, который мог бы поместиться в реальную машину, и поэтому Union-Find работает фактически за константу на операцию. Тарьян также показал, что эта оценка оптимальна: ни одна структура на указателях не может работать лучше в худшем случае.

Задача о связности

**Задача:** есть N компьютеров. Иногда соединяем два кабелем. Быстро отвечать: связаны ли A и B (напрямую или через другие)?

**Наивный подход:** BFS/DFS для проверки связности = O(V+E) на каждый запрос. При миллионах запросов - медленно!

**Union-Find** отвечает на connected(a,b) почти за O(1)!

Наивная реализация

**Идея:** каждое множество - дерево. Корень = представитель множества.

**Проблема:** дерево может вырождаться в список → find = O(n)

Оптимизация: Path Compression

**Path Compression:** при find прицепляем все узлы пути напрямую к корню.

Оптимизация: Union by Rank

**Union by Rank:** при объединении меньшее дерево присоединяем к большему.

**С обеими оптимизациями:** O(α(n)) ≈ O(1) на операцию! α - обратная функция Аккермана (растёт крайне медленно, < 5 для любых практических n).

Применения Union-Find

• **Сети** - динамическая связность компьютеров
• **Обработка изображений** - объединение пикселей в регионы
• **Минимальное остовное дерево** - алгоритм Крускала
• **Социальные сети** - компоненты связности друзей
• **Percolation** - моделирование просачивания

Union-Find

• find(x) - найти представителя множества
• union(x, y) - объединить два множества
• Path compression: узлы → прямо к корню
• Union by rank: меньшее к большему
• С обеими: O(α(n)) ≈ O(1)

Следующие темы

От графовых алгоритмов переходим к комбинации структур для эффективного кеширования.

• LRU Cache — Hash + Linked List

Связанные уроки

• ds-16-graphs-intro — Графы задают задачу связных компонент, которую решает структура
• alg-17-mst — Алгоритм Краскала для MST использует Union-Find для проверки циклов
• ds-17-graph-algorithms — Добавляет динамическую связность сверх статического обхода графа
• alg-03-amortized — Анализ сжатия путей опирается на амортизированную сложность
• db-23-sharding — Группировка строк в шарды похожа на объединение элементов в множества
• alg-13-dfs