Реализация алгоритма Крускала: структура Union-Find

Одной из основных задач графов является поиск множества связных компонент. В главе 3 рассматривались алгоритмы с линейным временем, использующие поиск BFS и DFS для нахождения компонент связности графа.

В этом разделе будет рассмотрена ситуация, в которой граф развивается по- средством добавления ребер. Другими словами, граф имеет фиксированный набор узлов, но со временем между некоторыми парами узлов появляются новые ребра. Требуется обеспечить хранение множества компонент связности такого графа в процессе эволюции. При добавлении в граф нового ребра было бы нежелательно заново вычислять компоненты связности. Вместо этого мы воспользуемся струк- турой данных, называемой структурой Union-Find; эта структура позволяет хранить информацию компонент с возможностью быстрого поиска и обновления.

Именно такая структура данных необходима для эффективной реализации алгоритма Крускала. При рассмотрении каждого ребра e = (v, w) необходимо эффективно идентифицировать компоненты связности, содержащие v и w. Если эти компоненты различны, то пути между v и w не существует и ребро e следует включить; но если компоненты совпадают, то путь v-w существует на ранее вклю- ченных ребрах, поэтому ребро e опускается. При включении e структура данных также должна обеспечивать эффективное слияние компонент v и w в одну новую компоненту.

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

Еще по теме Реализация алгоритма Крускала: структура Union-Find:

  1. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  2. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  3. АЛГОРИТМ УДАЧИ
  4. АЛГОРИТМ
  5. Алгоритм исцеления:
  6. Алгоритм избавления от боли
  7. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  8. Алгоритм обработки результатов.
  9. 2. Специфика и алгоритмы работы с источниками.
  10. СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
  11. Э. ТАНЕНБАУМ, А. ВУДХАЛЛ. ОПЕРАЦИОННЫЕ СИСТЕМЫ Разработка и реализация 3-е издание, 2007
  12. Глава 6. Реализация права
  13. 4.2. Реализация
  14. 4. Реализация прав по ипотеке
  15. 3.3. Дальнейшая реализация проекта