9. fejezet - Diszjunkt halmazok

Bizonyos feladattípusok esetén szükség van arra, hogy n különálló elemet diszjunkt halmazokba csoportosítsunk. Ekkor a következő két műveletetre lesz szükségünk:

– meg kell mondanunk, hogy két adott elem ugyanabba a diszjunkt halmazba tartozik-e vagy sem;

– két diszjunkt halmazt egyesítenünk kell.

Minden diszjunkt halmazban van egy kijelölt elem, ez a halmaz képviselője (reprezentánsa). Rendezett halmaz esetén ez lehet például a legkisebb elem. Az a fontos, hogy ha a halmaz képviselőjét keressük, minden eleméből kiindulva ugyanahhoz a képviselőhöz jussunk el. Ehhez a következő eljárásokat, függvényeket kell elkészítenünk:

HALMAZT-KÉSZÍT(x)

egy új halmazt hoz létre, melynek a képviselője x lesz

EGYESÍT(x,y)

azt a két halmazt, melynek képviselője x ill. y, egyesíti egy új halmazba

HALMAZT-KERES(x)

visszadja az x-et tartalmazó halmaz képviselőjét

9.1. Láncolt listás ábrázolás

A diszjunkt halmazok egy egyszerű ábrázolása az, ahol a halmazokat láncolt listaként ábrázoljuk.

9.1. ábra - Láncolt listás ábrázolás

Láncolt listás ábrázolás


Ekkor érdemes minden egyes rekordot kiegészíteni egy mutatóval, amely a halmaz reprezentánsára mutat. Ebben az esetben a mind a HALMAZT-KÉSZÍT, mind a HALMAZT-KERES bonyolultsága O(1). Az EGYESÍT műveletnél abban a listában, melyet a másik lista mögé fűzünk, minden egyes elemnél át kell állítani a képviselőt jelző mutatót. Ezért ésszerűbb a rövidebb listát a hosszabb mögé fűzni. Ezzel az összesen n elemet tartalmazó halmaz esetén m HALMAZT-KÉSZÍT, HALMAZT-KERES, EGYESÍT művelet bonyolultsága O(m + ln(n)).