Disjunkint set system

Kokeneet kirjoittajat eivät ole vielä tarkistaneet sivun nykyistä versiota, ja se voi poiketa merkittävästi 22. kesäkuuta 2017 tarkistetusta versiosta . tarkastukset vaativat 13 muokkausta .

Disjoint-set system ( eng. disjoint-set tai union-find -tietorakenne ) on tietorakenne , jonka avulla voit hallita elementtijoukkoa, joka on jaettu disjoint-alijoukkoon. Tässä tapauksessa kullekin osajoukolle määritetään sen edustaja - tämän osajoukon elementti. Abstrakti tietorakenne määritellään kolmen toiminnon joukolla: . ${\displaystyle \{\mathrm {Union} ,\mathrm {Find} ,\mathrm {MakeSet} \))$

Sitä käytetään yhdistettyjen komponenttien tallentamiseen kaavioihin , erityisesti Kruskalin algoritmi tarvitsee samanlaisen tietorakenteen tehokkaaseen toteutukseen.

Määritelmä

Olkoon äärellinen joukko, joka on jaettu ei-leikkaaviin osajoukkoon ( luokkiin ) : $S$ $X_{i}$

S=X_{0}\cup X_{1}\cup X_{2}\cup \ldots \cup X_{k}:X_{i}\cap X_{j}=\varnothing \quad \forall i ,j\in \lsulku 0,1,\ldots ,k\rbrace ,i\neq j

Jokaiselle osajoukolle on määritetty edustaja . Vastaava disjunktijoukkojen järjestelmä tukee seuraavia toimintoja: $X_{i}$ $r_{i}\in X_{i}$

$\mathrm {MakeSet} (x)$ : luo elementille uuden osajoukon. Määrittää saman elementin luodun osajoukon edustajaksi. $x$
$\mathrm {Union} (r,s)$ : yhdistää molemmat edustajiin kuuluvat osajoukot ja , ja nimeää uuden osajoukon edustajan. $r$ $s$ $r$
$\mathrm {Etsi} (x)$ : Määrittää osajoukon, johon elementti kuuluu, ja palauttaa sen edustajan. $x\in S$

Algoritminen toteutus

Triviaali toteutus tallentaa hakemistotaulukon elementtien ja edustajien omistajuuden . Käytännössä puujoukkoja käytetään useammin . Tämä voi merkittävästi lyhentää Etsi -toiminnon aikaa . Tässä tapauksessa edustaja kirjoitetaan puun juureen ja luokan loput elementit sen alapuolella oleviin solmuihin. $S$ $r_{i}$

$\mathrm {Union} (r,s)$ : ripustaa alemman puun juuren korkeamman puun juuren alle. Jos tästä tulee ali , molemmat solmut vaihdetaan. $r$ $s$
$\mathrm {Etsi} (x)$ : vie polun puun juurelle ja palauttaa sen (juuri tässä tapauksessa edustaa). $x$

Heuristiikka

Union-By-Size- , Union-By-Height- , Random -Union- heuristiikkaa ja polun pakkausta voidaan käyttää nopeuttamaan liitos- ja hakutoimintoja.

Union-By-Size -heuristisessa toimenpiteen aikana pienemmän puun juuri ripustetaan suuremman puun juuren alle. Tämä lähestymistapa säilyttää puun tasapainon. Kunkin alipuun syvyys ei voi olla suurempi kuin . Tätä heuristiikkaa käytettäessä pahimman mahdollisen Etsi -toiminnon aika kasvaa arvosta . Tehokkaan toteutuksen varmistamiseksi on ehdotettu, että puun solmujen lukumäärä tallennetaan juureen. $\mathrm {Union} (r,s)$ $T$ $\log \left|T\right|$ $O(\log n)$ $Päällä)$

Union-By-Height -heuristiikka on samanlainen kuin Union-By-Size , mutta käyttää puun korkeutta koon sijaan.

Random-Union- heuristiikka käyttää sitä tosiasiaa, että on mahdollista olla käyttämättä lisämuistia puun solmujen määrän tallentamiseen: riittää, että valitaan juuri satunnaisesti - tämä ratkaisu antaa satunnaisille kyselyille nopeuden, joka on melko verrattavissa muihin. toteutukset. Jos kyselyitä, kuten "yhdistä suuri joukko pieneen", on kuitenkin useita, tämä heuristinen parantaa odotettua arvoa (eli keskimääräistä ajoaikaa) vain kaksinkertaiseksi, joten sen käyttöä ei suositella ilman polun pakkausheuristiikka. $Päällä)$

Reitin pakkausheuristiikkaa käytetään nopeuttamaan toimintaa . Jokaisen uuden haun yhteydessä kaikki elementit, jotka ovat polulla juuresta haluttuun elementtiin, ripustetaan puun juuren alle. Tässä tapauksessa Etsi -toiminto toimii keskimäärin , missä on Ackerman-funktion käänteisfunktio . Näin voit nopeuttaa työtä merkittävästi, koska kaikilla käytännössä käytetyillä arvoilla se vaatii alle 5:n. $\mathrm {Etsi} (x)$ $\alpha (n)$ $\alpha$ $\alpha$

Toteutusesimerkki

Toteutus C++:ssa:

const int MAXN = 1000 ; int p [ MAXN ], sijoitus [ MAXN ]; void MakeSet ( int x ) { p [ x ] = x ; sijoitus [ x ] = 0 ; } int Etsi ( int x ) { return ( x == p [ x ] ? x : p [ x ] = Etsi ( p [ x ]) ); } void Union ( int x , int y ) { if ( ( x = Etsi ( x )) == ( y = Etsi ( y )) ) paluu ; jos ( sijoitus [ x ] < sijoitus [ y ] ) p [ x ] = y ; else { p [ y ] = x ; jos ( sijoitus [ x ] == sijoitus [ y ] ) ++ sijoitus [ x ]; } }

Toteutus Free Pascalissa:

const MAX_N = 1000 ; var Parent , Rank : matriisi [ 1..MAX_N ] LongInt : stä ; _ proseduurin vaihto ( var x , y : LongInt ) ; var tmp : LongInt ; alkaa tmp := x ; x : = y y := tmp ; loppu ; menettely MakeSet ( x : LongInt ) ; alkaa Vanhempi [ x ] := x ; Sijoitus [ x ] := 0 ; loppu ; toiminto Etsi ( x : LongInt ) : LongInt ; alkaa jos ( Vanhempi [ x ] <> x ) sitten Vanhempi [ x ] := Etsi ( vanhempi [ x ] ) ; Poistu ( Parent [ x ] ) ; loppu ; menettely Unioni ( x , y : LongInt ) ; alkaa x := Etsi ( x ) ; y := Etsi ( y ) ; jos ( x = y ) sitten poistu () ; if ( Sijoitus [ x ] < Sijoitus [ y ] ) sitten swap ( x , y ) ; Vanhempi [ y ] := x ; if ( Sijoitus [ x ] = Sijoitus [ y ] ) sitten inc ( Sijainti [ x ] ) ; loppu ;

Katso myös

Erillisten joukkojen metsä

Kirjallisuus

Galler, Bernard A. ja Michael J. Fisher. "Parannettu vastaavuusalgoritmi." // Communications of the ACM , 7.5 (1964): 301-303. (Englanti)
Tarjan, Robert E. ja Jan Van Leeuwen. "Pahimman tapauksen analyysi joukkoliitosalgoritmeista." // Journal of the ACM 31.2 (1984): 245-281. (Englanti)
Thomas Kormen ym. Algoritmit: Rakentaminen ja analyysi = Johdanto algoritmeihin. - 2. painos - M .: "Williams" , 2006. - S. 1296. - ISBN 0-07-013151-1 .

Linkit

Union-Find / Kevin Wayne , Pearson-Addison Wesley
Luku 22: Tietorakenteet epäyhtenäisille joukoille / Johdatus algoritmeihin, Thomas H. Cormen, Charles E. Leiserson ja Ronald L. Rivest
Joidenkin tietorakenteiden työn visualisointi ei-leikkautuville joukoille / ITMO
Disjoint-joukkojen käyttöönotto C++ Boost Libraries -kokoelmassa , 2006

Tietorakenteet
Luettelot	joukko yksittäin linkitetty lista kaksoislinkitetty lista Passilista
puut	B-puu Binäärihakupuu AVL puu Puna-musta puu pino
Laskee	Suunnattu graafi Suunnattu asyklinen graafi Binääripäätöskaavio Hypergraph
Muut	Hash-taulukko Pino