Комбинаторные алгоритмы для программистов



             

Множества и мультимножества - часть 3


Такой структурой данных является представление в виде леса с указателями отца, как показано на рис. 4.5 лекции 4. Каждый элемент
s_i
множества будет узлом леса, а отцом его будет элемент из того же подмножества, что и
s_i
. Если элемент не имеет отца, то есть является корнем, то он будет именем своего подмножества. В соответствии с этим разбиение 5.1 может быть представлено так:

Представление разбиения

Рис. 6.1.  Представление разбиения

При таком представлении процедура (операция)

FIND(x)
состоит в переходах по указателям отцов от
x
до корня, то есть имени, его подмножества. Процедура (операция)
UNION(x,y)
состоит в связывании вместе некоторым образом деревьев, имеющих корни
x
и
y
. Например, такую связь можно осуществить, сделав
y
отцом
x
.

После

u
операций объединения наибольшее из возможных подмножеств, получающихся в результате разбиения
S
, будет содержать
u + 1
элементов. Поскольку каждое объединение уменьшает число подмножеств на единицу, последовательность операций может содержать не более
n-1

объединений, откуда

u \leqslant n - 1
. Так как каждая операция объединения изменяет имя подмножества, содержащего некоторые элементы, можно считать, что каждому объединению предшествует по крайней мере одно отыскание, в связи с чем естественно предположить, что
f \geqslant u
. Выясним, насколько эффективно можно выполнить последовательность из
u \leqslant n - 1
операций объединения, перемешанных с
f \geqslant u
операциями отыскания. Время, требуемое на операции объединения, очевидно, пропорционально
u
, потому что необходимая для каждой операции объединения переделка некоторых указателей требует фиксированного количества работы. Поэтому сосредоточим свое внимание на времени, требуемом для
f
операций отыскания.

Если операция

UNION(x,y)
выполняется путем назначения
x
отцом
y
, то после
u
операций объединения может получиться лес, показанный ниже.

 u+1\left\{\cfig <scale=0.8> {06-02.eps}\right.\qquad \underbrace{\circ\;\circ\;\ldots\circ}_{n-u-1} \vspace{-3mm}

В этом случае, если

f
операций отыскания выполняются после всех операций объединения и каждый поиск начинается внизу цепи из
u + 1
элементов множества, то ясно, что время, требуемое на операции отыскания, будет пропорционально
f \cdot (u + 1)
. Очевидно, оно не может быть больше, чем константа, умноженная на
f \cdot (u + 1)
.Можно существенно уменьшить эту оценку.




Содержание  Назад  Вперед