Структуры данных и модели вычислений
Примеры использования разделенных множеств
Пример 1.
Рассмотрим задачу выделения компонент связности неориентированного графа. Напомним, что компонентой связности называется максимальное по включению подмножество вершин графа такое, что любые две его вершины связаны цепью. Полагаем, что вершины графа пронумерованы числами и каждое ребро представлено парой () номеров вершин. Предполагаем также, что множество ребер не пусто.
Алгоритм выделения компонент связности неориентированного графа
Очевидно, построенные подмножества коллекции будут представлять искомые компоненты связности. Используя названия основных операций над коллекцией разделенных множеств, представленный выше алгоритм можно записать в следующем виде:
Пример 2.
Рассмотрим неориентированный связный граф без петель, ребрам которого приписаны в качестве весов положительные вещественные числа. Требуется построить остовное дерево, накрывающее все вершины графа и имеющее минимальный суммарный вес входящих в него ребер. Итак, пусть заданный граф имеет множество вершин, пронумерованных числами , и множество ребер. Каждому ребру из множества
поставлена в соответствие пара его концевых вершин и число — его вес. Для решения этой задачи были предложены различные алгоритмы. Мы рассмотрим алгоритм, который разработал Крускал.
Алгоритм Крускала
Заметим, что в процессе работы алгоритма в множестве будут находиться ребра, составляющие ациклический подграф исходного графа, являющийся лесом, состоящим из некоторого числа деревьев. Отсутствие циклов гарантируется проверкой "Если " в пункте 6 описанного алгоритма. Фактически при происходит объединение двух поддеревьев в одно дерево с помощью ребра , найденного на шаге 3.
Если исходный граф связен, как сказано в постановке задачи, то построенное с помощью такого алгоритма множество будет, очевидно, представлять дерево, накрывающее все вершины исходного графа. Доказательство того, что суммарный вес входящих в него ребер будет минимальным, можно найти в разделе "Графы".
В алгоритме естественным образом используется структура разделенных множеств. Обратим внимание на операцию поиска в множестве
ребра
с минимальным весом. Эффективность этой операции во многом зависит от выбора структуры данных для хранения множества . Приемы эффективного выполнения этой операции рассмотрены в разделе "Приоритетные очереди".
