Приклади використання розділених множин
Приклад 1. Розглянемо задачу виділення компонент зв'язності неориентированного графа. Нагадаємо, що компонентою зв'язності називається максимальне по включенню підмножина вершин графа таке, що будь-які дві його вершини пов'язані ланцюгом. Вважаємо, що вершини графа пронумеровані числами і кожне ребро представлено парою () номерів вершин. Припускаємо також, що безліч ребер не порожньо.
Алгоритм виділення компонент зв'язності неориентированного графа
Очевидно, побудовані підмножини колекції представлятимуть шукані компоненти зв'язності. Використовуючи назви основних операцій над колекцією розділених множин. представлений вище алгоритм можна записати в наступному вигляді:
Приклад 2. Розглянемо неорієнтований зв'язний граф без петель, ребрах якого приписані в якості ваг позитивні речові числа. Потрібно побудувати кістяк. накриває все вершини графа і має мінімальний сумарний вага входять до нього ребер. Отже, нехай заданий граф має безліч вершин, пронумерованих числами, і безліч ребер. Кожному ребру з множини поставлена у відповідність пара його кінцевих вершин і число - його вага. Для вирішення цього завдання були запропоновані різні алгоритми. Ми розглянемо алгоритм. який розробив Круськала.
Зауважимо, що в процесі роботи алгоритму в безлічі знаходитимуться ребра, складові ациклический підграф вихідного графа, що є лісом, що складається з певної кількості дерев. Відсутність циклів гарантується перевіркою "Якщо" в пункті 6 описаного алгоритму. Фактично при відбувається об'єднання двох піддерев в одне дерево за допомогою ребра, знайденого на кроці 3.
Якщо вихідний граф зв'язний, як сказано в постановці завдання, то побудоване за допомогою такого алгоритму безліч буде, очевидно, представляти дерево. накриває все вершини вихідного графа. Доказ того, що сумарна вага входять до нього ребер буде мінімальним, можна знайти в розділі "Графи".
В алгоритмі природним чином використовується структура розділених множин. Звернемо увагу на операцію пошуку в безлічі ребра з мінімальною вагою. Ефективність цієї операції багато в чому залежить від вибору структури даних для зберігання безлічі. Прийоми ефективного виконання цієї операції розглянуті в розділі "Пріоритетні черги".
Подання розділених множин за допомогою масиву
Нехай - безліч, з елементів якого буде будуватися колекція розділених підмножин. Одним з очевидних способів представлення колекції є уявлення її за допомогою масиву. При такому способі для кожного елемента у відповідній (-й) осередку масиву поміщаємо ім'я (канонічний елемент) того підмножини, якому належить елемент. Якщо елемент не належить жодному з підмножин колекції, то в -ю осередок записуємо 0.
Реалізація операцій за допомогою масиву
Позначимо через масив довжини, за допомогою якого будемо представляти колекцію. Порожня колекція представляється масивом, заповненим нулями.
Операція СТВОРИТИ () здійснюється записом елемента в клітинку з номером. Час виконання операції -.
Операція ОБ'ЄДНАТИ () здійснюється наступним чином. Проглядаються елементи масиву, і в ті осередки, в яких було записано ім'я, заноситься нове ім'я -. Отже, ім'ям новоутвореного підмножини буде, а перестане бути ім'ям якого-небудь підмножини. Очевидно, час виконання цієї операції -.
Операція ШУКАТИ () видає в якості вміст елемента з номером в масиві. Час виконання операції -.
При такій реалізації розділених множин. очевидно, що час виконання довільних операцій, серед яких операцій ОБ'ЄДНАТИ, є величина.