  ̌      ̌   
P 49 (2021/2022) 122
Podatkovna struktura za
disjunktne množice
D S
Pri reševanju praktičnih problemov z računalni-
škimi algoritmi pogosto naletimo na naslednjo si-
tuacijo: dano je večje število objektov, ki jih zdru-
žujemo v vedno večje množice, tako da v vsakem
trenutku vsak objekt pripada natanko eni množici.
Pri tem na trenutni skupini množic pogosto izva-
jamo naslednji dve operaciji:
preverjanje, ali dva objekta x in y pripadata isti
množici, in
združevanje množic, ki jima pripadata objekta x
in y .
Običajno začetno stanje je takšno, da vsak objekt
predstavlja samostojno množico, te pa nato zapore-
doma združujemo.
Za množici, ki nimata skupnih elementov, pravi-
mo, da sta disjunktni (disjoint). Objekti so torej v
vsakem trenutku razporejeni v skupino disjunktnih
množic, katerih število se z njihovim združevanjem
samo manjša. Z naivno implementacijo disjunktnih
množic lahko dosežemo hitro izvajanje ene od ope-
racij, ne pa obeh hkrati. Če npr. disjunktne mno-
žice predstavimo s seznami elementov, bo združe-
vanje množic hitro, za preverjanje pripadnosti ele-
mentov isti množici pa bomo morali izvesti pregled
seznama in pri tem v splošnem opraviti reda N pri-
merjav, kjer je N število elementov. Po drugi strani
bi bila implementacija s poljem, v katerem hranimo
oznake množic za posamezne elemente, neučinko-
vita pri združevanju množic, kjer bi morali posodo-
biti reda N oznak v polju. Potrebujemo torej boljšo
rešitev. V tem prispevku bomo opisali implemen-
tacijo podatkovne strukture za disjunktne množice
(disjoint-set data structure), ki omogoča učinkovito
izvajanje zaporedja prej opisanih operacij. Ker to do-
sežemo z implementacijo dveh metod, imenovanih
IŠČI (FIND) in UNIJA (UNION), to podatkovno struk-
turo v literaturi pogosto imenujejo tudi podatkovna
struktura UNIJA-IŠČI (union-find data structure).
Pri implementaciji podatkovne strukture za dis-
junktne množice je vsaka množica predstavljena kot
drevo, v katerem so elementi množice hierarhično
povezani preko kazalcev na starše, pri čemer koren
drevesa kaže sam nase. Kot primer vzemimo mno-
žico objektov, ki so označeni s celimi števili od 0
do 7. Če so ti objekti razdeljeni v tri disjunktne
množice t0,5,6u, t2,3,4,7u in t1u, lahko to grafično
ponazorimo s sliko 1. Oblika posameznih dreves je
lahko tudi drugačna in je odvisna od tega, v kakem
vrstnem redu smo množice združevali.
SLIKA 1.
Predstavitev disjunktnih množic z drevesi, v katerih so elementi
povezani s kazalci na starše. Reprezentativni element množice
je koren, ki kaže sam nase.
  ̌      ̌   
P 49 (2021/2022) 1 23
V podatkovni strukturi za disjunktne množice je
vsaka množica enolično določena z njenim reprezen-
tativnim elementom, ki je v tem primeru koren dre-
vesa. V nadaljevanju bomo zato za reprezentativni
element množice uporabljali kar krajši izraz koren
(root). Pripadnost dveh objektov isti množici lahko
ugotavljamo s preverjanjem enakosti njunih kore-
nov, pri združevanju dveh množic pa koren unije
postane eden od dosedanjih dveh korenov. Podat-
kovna struktura za disjunktne množice je torej neke
vrste nadstruktura ali gozd dreves, ki predstavljajo
posamezne disjunktne množice. Označitev objektov
z zaporednimi celimi števili od 0 naprej omogoča še
posebej elegantno programsko predstavitev dreves v
strnjenem polju A dolžine N , v katerem i-ti element
polja hrani oznako starša objekta i. Disjunktne mno-
žice s slike 1 bi lahko tako opisali s poljem na sliki 2.
SLIKA 2.
Zapis drevesnih struktur s slike 1 s poljem. Vrednost na polo-
žaju i v polju je indeks starša objekta i.
Ob inicializaciji podatkovne strukture za disjunk-
tne množice z N objekti je potrebno ustvariti N mno-
žic, katerih koreni (in hkrati edini elementi) so posa-
mezni objekti. Pri zgoraj opisani implementaciji s
poljem A je postopek zelo enostaven, potrebno je
le vsem objektom postaviti »kazalec« nase (algori-
tem 1).
Algoritem 1 Inicializacija disjunktnih množic
function INICIALIZACIJA(N)
for i Ð 0 . . .N´1 do
A[i] Ð i
end for
end function
Ključni metodi, ki ju implementira podatkovna
struktura za disjunktne množice, sta že omenjeni
IŠČI in UNIJA. Metoda IŠČI kot argument prejme
oznako objekta in vrne oznako korena disjunktne
množice, ki ji objekt pripada. Osnovna implementa-
cija metode je zelo preprosta, saj je potrebno le sle-
diti verigi staršev od danega objekta navzgor proti
korenu. Slednjega prepoznamo po tem, da kaže sam
nase. Postopek je v obliki rekurzivne funkcije zapi-
san v algoritmu 2, možna pa je tudi iterativna im-
plementacija z enako časovno zahtevnostjo, ki zapo-
redje prednikov hrani na skladu.
Algoritem 2 Osnovna metoda IŠČI
function IŠČI(x)
if A[x]=x then
return x
else
return IŠČI(A[x])
end if
end function
Problem zgornjega postopka je v tem, da bomo ob
naslednjem klicu IŠČI z istim argumentom spet mo-
rali prehoditi isto zaporedje kazalcev, kar postane
ob velikem številu ponavljajočih se klicev neučinko-
vito. Podatkovna struktura za disjunktne množice
zato uporabi t. i. stiskanje poti (path compression),
pri katerem ob vračanju iz rekurzije vsem objektom
na poti postavimo kazalec na starša na najdeni koren
množice, kot prikazuje algoritem 3.
Algoritem 3 Metoda IŠČI s stiskanjem poti
1: function IŠČI(x)
2: if A[x]=x then
3: return x
4: else
5: A[x] Ð IŠČI(A[x])
6: return A[x]
7: end if
8: end function
Princip delovanja stiskanja poti prikažimo na
zgledu disjunktne množice na levi strani slike 3. Po
izvedbi klica IŠČI(0) bo novo stanje drevesa in pri-
padajočega polja takšno, kot je prikazano na desni
strani slike. Vsak naslednji klic IŠČI(0) ali IŠČI(5)
se bo sedaj zaključil v enem koraku.
S tako definirano metodo IŠČI lahko preverjanje,
ali objekta x in y pripadata isti disjunktni množici,
izvedemo s primerjavo IŠČI(x)=IŠČI(y).
Druga ključna operacija na podatkovni strukturi
za disjunktne množice je združevanje ali unija dveh
množic. Metoda UNIJA kot argument prejme dva
  ̌      ̌   
P 49 (2021/2022) 124
SLIKA 3.
Stiskanje poti pri klicu IŠČI(0) poveže vse elemente preho-
jene verige neposredno s korenom množice, zaradi česar bodo
naslednji klici IŠČI bolj učinkoviti.
objekta in izvede združevanje disjunktnih množic,
ki jima ta objekta pripadata. Če objekta že pripa-
data isti disjunktni množici, se ne zgodi nič. V na-
sprotnem primeru je potrebno povezati drevesi obeh
množic tako, da koren ene množice priključimo kot
naslednika korenu druge množice, ki s tem postane
koren celotne unije. Združevanje dveh dreves si že-
limo izvesti tako, da bo imelo drevo unije čim manj-
šo višino, saj bo povprečna dolžina poti v takšnem
drevesu manjša in bo iskanje korena zato učinkovi-
tejše. Kadar torej združujemo dve drevesi različnih
višin, je potrebno nižje drevo priključiti višjemu, ka-
terega višina se zaradi tega ne spremeni (slika 4 levo).
Če pa združujemo dve drevesi enake višine, je smer
priključevanja nepomembna, višina združenega dre-
vesa pa bo za ena večja (slika 4 desno).
Za učinkovito implementacijo unije je torej potreb-
no voditi višine dreves. Ker pa se višina drevesa za-
radi stiskanja poti lahko spremeni tudi ob izvajanju
klicev IŠČI, je beleženje in posodabljanje točne vi-
šine dreves nepraktično. V podatkovni strukturi za
disjunktne množice zato vodimo samo range (rank)
posameznih dreves. Rang drevesa je zgornja meja
višine drevesa, ki ne odraža nujno njegove dejanske
višine, ampak samo njeno največjo možno vrednost.
Pri združevanju množic priključimo množico z niž-
jim rangom tisti z višjim rangom, kar imenujemo
unija po rangu (union by rank). Za beleženje ran-
gov uporabimo ločeno polje R, v katerem so veljavni
rangi zapisani samo pri objektih, ki so koreni svojih
disjunktnih množic (algoritem 4). Začetne vrednosti
vseh rangov pri inicializaciji podatkovne strukture
za disjunktne množice (algoritem 1) postavimo na 0.
Algoritem 4 Unija po rangu
1: function UNIJA(x,y)
2: a Ð IŠČI(x)
3: b Ð IŠČI(y)
4: if a‰b then
5: if R[a] ě R[b] then
6: A[b] Ð a
7: if R[a] = R[b] then
8: R[a] = R[a] + 1
9: end if
10: else
11: A[a] Ð b
12: end if
13: end if
14: end function
Zgled zaporednega združevanja disjunktnih mno-
žic je prikazan na sliki 5, pri čemer so rangi posame-
znih množic zapisani ob korenskem vozlišču.
V praktičnih aplikacijah običajno želimo za posa-
mezne disjunktne množice voditi še dodatne opisne
parametre, kot je npr. število objektov v množici.
Tudi sami objekti imajo lahko lastne številske atri-
bute, ki jih želimo pri združevanju množic na dolo-
čen način zlivati (npr. vsota ali povprečje vrednosti
atributa elementov množice). Vsako od teh statistik
lahko beležimo z ločenim dodatnim poljem, v kate-
rem trenutno vrednost za vsako množico hranimo
na indeksu njenega korena (na podoben način kot
SLIKA 4.
Pri združevanju disjunktnih množic v primeru razlǐcno visokih
dreves manjše drevo priključimo večjemu, zato da višina dre-
vesa ostane enaka (a). V primeru enako visokih dreves je smer
povezovanja nepomembna, višina združenega drevesa pa se
poveča za ena (b).
  ̌      ̌   
P 49 (2021/2022) 1 25
SLIKA 5.
Primer zaporednega izvajanja unije
po rangu. V zadnjem koraku se pri is-
kanju korena disjunktne množice za
objekt 2 izvede tudi stiskanje poti.
Bodimo pozorni na to, da je vrstni
red argumentov klica UNIJA pomem-
ben, ko združujemo drevesa z ena-
kim rangom (npr. klic UNIJA(2,3)
v tretjem koraku bi tvoril drugačno
drevo).
SLIKA 6.
Predstavitev stikov (povezave) med osebami (vozlišča) z gra-
fom. Vsak povezan del grafa predstavlja neodvisen mehurček.
prej rang v polju R). Včasih pa nas tudi zanima samo
število disjunktnih množic na koncu, kar je prav tako
enostavno ugotoviti – po zaključku združevanja se
sprehodimo skozi polje A in preštejemo primere, ko
je Aris “ i.
Najbolj znan primer aplikacije podatkovne struk-
ture za disjunktne množice je vodenje minimalnih
vpetih dreves pri Kruskalovem algoritmu, o katerem
je bilo v Preseku v preteklosti že pisano. Našo obrav-
navo zato zaključimo z naslednjim, za trenutne čase
precej aktualnim primerom: V populaciji N oseb raz-
saja prenosljiva virusna bolezen, ki pa jo oboleli pre-
boli v sedmih dneh. Ker se testiranje še ni začelo, se
ne ve, kdo je okužen, imamo pa podatke o tem, kdo
je bil s kom v stiku v zadnjih sedmih dneh. Da pre-
prečimo nadaljnje širjenje bolezni, želimo oblikovati
SLIKA 7.
Postopek reševanja problema z mehurčki
         
P 49 (2021/2022) 126
»mehurčke«, tj. skupine oseb, ki so bile v omenjenem
času v neposrednem ali posrednem stiku. Vsak stik
je podan kot par oseb px,yq, ki sta bili v stiku. Za-
radi zaščite osebnih podatkov so osebe označene s
števili od 0 do N ´ 1. Zanima nas število mehurčkov
in velikost največjega mehurčka.
Kot zgled podajmo primer z osmimi osebami,
od katerih so bili v zadnjem tednu v stiku pari
p0,1q, p1,4q, p2,4q, p2,7q, p3,5q, p3,6q in p4,7q. Če ose-
be narišemo kot vozlišča grafa, stike pa kot povezave
med njimi, dobimo graf iz dveh ločenih delov (t. i. po-
vezani komponenti) na sliki 6, ki v tem primeru pred-
stavljata iskana mehurčka t0,1,2,4,7u in t3,5,6u.
Problem lahko rešimo, če mehurčke obravnavamo
kot disjunktne množice. Postopek reševanja prika-
zuje slika 7.
Na začetku je vsaka oseba v lastnem mehurčku,
vsak ugotovljeni stik pa predstavlja možen prenos
okužbe, zato je potrebno mehurčka oseb v stiku
združiti (razen če sta že v istem mehurčku). V zanki
zato obravnavamo zgoraj naštete stike in za vsak
stik px,yq izvedemo klic UNION(x,y). Število oseb
v mehurčku vodimo pri korenu pripadajoče disjunk-
tne množice, pri združevanju pa seštejemo vredno-
sti pri korenih obeh množic. Na sliki 7 so prikazane
vsebine polj A (indeksi staršev), R (rangi) in C (ve-
likosti disjunktnih množic). Po zaključku postopka
lahko ugotovimo, da sta osebi 0 in 3 korena dveh pre-
ostalih mehurčkov, od katerih je večji prvi (Cr0s “ 5).
Literatura
[1] T. H. Cormen, C. E. Leiserson, R. L. Rivest in
C. Stein, Introduction to Algorithms, 3. izdaja, The
MIT Press, 2009.
www.dmfa-zaloznistvo.si
www.obzornik.si
ˆ ˆ ˆ
̌

̌
 48/6
Pravilna rešitev nagra-
dne križanke iz šeste
številke Preseka letnika
48 je Butalci. Izmed pra-
vilnih rešitev so bili iz-
žrebani Marko Kubale
iz Rogaške Slatine, Anže
Mihelčič iz Kresnic in
Manja Ferme iz Celja, ki
bodo razpisane nagrade
prejeli po pošti.
ˆ ˆ ˆ