Коллекция алгоритмов

Разбиения множеств
     Многие алгоритмы используют представление множеств в виде набора непересекающихся подмножеств, которые можно по-разному комбинировать. Для этой цели можно воспользоваться средствами работы с множествами, имеющимися в современных языках программирования, однако их реализации не гарантируют, что различные подмножества действительно будут непересекающимися. Кроме того, средства обработки множеств имеются не во всех языках программирования. В этом параграфе мы рассмотрим способ реализации разбиений множеств на массивах. Подобные алгоритмы могут принести пользу при реализации алгоритма Крускала построения минимального остовного поддерева.
     Начнем с массива Parent, в котором под каждый элемент множества, с которым мы собираемся работать, отведена одна ячейка. Вначале мы полагаем значения всех элементов равными -1. Знак - означает здесь, что каждый элемент является корнем разбиения, а абсолютное значение 1 - что соответствующая часть разбиения состоит из одного элемента. При работе алгоритма значения ячеек будут меняться, и, скажем, значение -7 указывает на то, что соответствующий элемент является корнем части, состоящей из семи элементов. При добавлении элемента к части значение соответствующей ему ячейки добавляется к значению корня. Если, к примеру, пятый элемент добавляется к части, корень которой - восьмой элемент массива Parent, то в пятую ячейку записывается значение 8, а отрицательное содержимое восьмой ячейки будет увеличено по абсолютной величине, чтобы указать на появление дополнительного элемента. При объединении двух частей разбиения происходит изменение только корневых ячеек этих частей, поэтому каждый элемент массива ссылается на своего непосредственного предка.


     Рассмотрим разбиение, изображенное на рис. 1. Видно, что оно состоит из трех частей с корнями 5, 6 и 11. В этих ячейках записаны отрицательные значения, модули которых равны числу элементов в соответствующем разбиении. Во всех остальных ячейках хранятся номера их непосредственных предков. Если мы захотим объединить части с корнями 6 и 11, то нужно в ячейку Parent[11] занести значение 6 - новый корень объединенной части, а в ячейку 6 - значение -5, модуль которого равен числу элементов в объединении двух частей. Вот алгоритмы, реализующие эту структуру разбиений:
InitializePartition(N)
N	число элементов в множестве
for i = 1 to N do
	Parent[i] = -1
end for
			
     Как мы уже говорили, процедура инициализации просто заносит в каждую ячейку массива Parent значение -1, которое указывает, что каждый элемент составляет отдельную часть разбиения.
Union(i, j)
i, j	объединяемые части разбиения

totalElements = Parent[i] + Parent[j]
if Parent[i] >= Parent[i] + Parent[j] then
	Parent[i] = j
	Parent[j] = totalElements
else
	Parent[j] = i
	Parent[i] = totalElements
end if
			
     Функция Union выполняет объединение двух частей в одну. Сначала она подсчитывает общее число элементов в объединенной части. Затем она подсоединяет меньшую часть к большей. Напомним, что размеры частей указываются отрицательными числами, поэтому вариант then добавляет меньшую i-ую часть к большей j-ой части, а вариант else добавляет меньшую j-ую часть к большей i-ой части.
FindRoot(s)
s	элемент, для которого мы хотим найти корень части, 
его содержащий

result = s
while Parent[result] > 0 do
	resut = Parent[result]
end while
return result
			
     Процедура FindRoot начинает с ячейки Parent[s], в которой хранится номер непосредственного предка элемента s. Если это значение отрицательно, то s сам является корнем разбиения, и он возвращается в качестве результата. Если же s не является корнем, то мы заносим в переменную result значение непосредственного предка элемента s и проверяем, не является ли оно корнем. Эта последовательность действий повторяется, пока мы не обнаружим корень. Эффективность этого алгоритма можно повысить, если, вернувшись по пройденному пути, занести во все пройденные ячейки номер найденного корня. На такую работу уходит некоторое время, однако при последующих обращениях корень части, содержащей просмотренные элементы, будет найден быстрее.

Рейтинг@Mail.ru Rambler's Top100
Сайт управляется системой uCoz