Usammenhængende sæt system

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 22. juni 2017; checks kræver 13 redigeringer .

Disjoint-set system ( eng. disjoint-set , eller union-find data structure ) er en datastruktur, der giver dig mulighed for at administrere et sæt elementer, opdelt i usammenhængende delmængder. I dette tilfælde tildeles hver delmængde sin repræsentant - et element i denne delmængde. En abstrakt datastruktur er defineret af et sæt af tre operationer: . ${\displaystyle \{\mathrm {Union} ,\mathrm {Find} ,\mathrm {MakeSet} \))$

Den bruges til at gemme tilsluttede komponenter i grafer , især Kruskals algoritme har brug for en lignende datastruktur for effektiv implementering.

Definition

Lad en endelig mængde opdelt i ikke-skærende delmængder ( klasser ) : $S$ $X_{i}$

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

Hver delmængde tildeles en repræsentant . Det tilsvarende system af usammenhængende sæt understøtter følgende operationer: $X_{i}$ $r_{i}\in X_{i}$

$\mathrm {MakeSet} (x)$ : opretter et nyt undersæt til elementet. Angiver det samme element som en repræsentant for den oprettede delmængde. $x$
$\mathrm {Union} (r,s)$ : kombinerer begge delmængder, der tilhører repræsentanter og , og udpeger repræsentanten for den nye undergruppe. $r$ $s$ $r$
$\mathrm {Find} (x)$ : Specificerer for den delmængde, som elementet tilhører, og returnerer dets repræsentant. $x\i S$

Algoritmisk implementering

En triviel implementering gemmer ejerskabet af elementer fra og repræsentanter i et indeksarray . I praksis bruges træsæt oftere . Dette kan reducere den tid, der kræves til Find -operationen betydeligt . I dette tilfælde skrives repræsentanten til roden af træet, og de resterende elementer i klassen skrives til noderne under den. $S$ $r_{i}$

$\mathrm {Union} (r,s)$ : hænger roden af et lavere træ under roden af et højere træ. Hvis dette bliver et barn af , skiftes begge noder. $r$ $s$
$\mathrm {Find} (x)$ : tager stien fra til roden af træet og returnerer den (roden i dette tilfælde er en repræsentant). $x$

Heuristik

Union-By-Size , Union-By-Height , Random-Union heuristik og stikomprimering kan bruges til at fremskynde Union og Find -operationer.

I Union-By-Size heuristikken bliver roden af det mindre træ under operationen hængt under roden af det større træ. Denne tilgang bevarer træets balance. Dybden af hvert undertræ må ikke overstige . Ved at bruge denne heuristik øges den værst tænkelige Find -operationstid fra til . For en effektiv implementering foreslås det at gemme antallet af noder i træet ved roden. $\mathrm {Union} (r,s)$ $T$ $\log \left|T\right|$ $O(\log n)$ $På)$

Heuristikken Union-By-Height ligner Union-By-Size , men bruger træets højde i stedet for størrelsen.

Random-Union- heuristikken bruger det faktum, at det er muligt ikke at bruge yderligere hukommelse på at gemme antallet af noder i træet: det er nok at vælge roden tilfældigt - denne løsning giver en hastighed på tilfældige forespørgsler, der er ret sammenlignelig med andre implementeringer. Men hvis der er mange forespørgsler som "flet et stort sæt med et lille", forbedrer denne heuristik den forventede værdi (det vil sige den gennemsnitlige køretid) med kun en faktor to, så det anbefales ikke at bruge det uden banekomprimeringsheuristikken. $På)$

Stikomprimeringsheuristikken bruges til at fremskynde operationen . Ved hver ny søgning bliver alle elementer, der er på stien fra roden til det ønskede element, hængt under træets rod. I dette tilfælde vil Find -operationen fungere i gennemsnit , hvor er den omvendte funktion af Ackerman-funktionen . Dette giver dig mulighed for at fremskynde arbejdet betydeligt, da det for alle værdier, der bruges i praksis, tager en værdi mindre end 5. $\mathrm {Find} (x)$ $\alpha (n)$ $\alfa$ $\alfa$

Implementeringseksempel

Implementering i C++:

const int MAXN = 1000 ; int p [ MAXN ], rang [ MAXN ]; void MakeSet ( int x ) { p [ x ] = x ; rang [ x ] = 0 ; } int Find ( int x ) { return ( x == p [ x ] ? x : p [ x ] = Find ( p [ x ]) ); } void Union ( int x , int y ) { if ( ( x = Find ( x )) == ( y = Find ( y )) ) returnere ; hvis ( rang [ x ] < rang [ y ] ) p [ x ] = y ; andet { p [ y ] = x ; if ( rang [ x ] == rang [ y ] ) ++ rang [ x ]; } }

Implementering i Free Pascal:

const MAX_N = 1000 ; var Parent , Rank : array [ 1..MAX_N ] af LongInt ; _ _ procedure swap ( var x , y : LongInt ) ; var tmp : LongInt ; begynde tmp := x ; x : = y y := tmp ; ende ; procedure MakeSet ( x : LongInt ) ; begynde Forælder [ x ] := x ; Rang [ x ] := 0 ; ende ; function Find ( x : LongInt ) : LongInt ; begynde hvis ( Forælder [ x ] <> x ) så Forælder [ x ] := Find ( Forælder [ x ] ) ; Afslut ( forælder [ x ] ) ; ende ; procedure Union ( x , y : LongInt ) ; begynde x := Find ( x ) ; y := Find ( y ) ; hvis ( x = y ) så afslut () ; hvis ( Ranger [ x ] < Ranger [ y ] ) så swap ( x , y ) ; Forælder [ y ] := x ; hvis ( Rank [ x ] = Rang [ y ] ) derefter inc ( Rang [ x ] ) ; ende ;

Se også

Skov af usammenhængende sæt

Litteratur

Galler, Bernard A. og Michael J. Fisher. "En forbedret ækvivalensalgoritme." // Communications of the ACM , 7.5 (1964): 301-303. (Engelsk)
Tarjan, Robert E. og Jan Van Leeuwen. "Worst-case analyse af sæt unionsalgoritmer." // Journal of the ACM 31.2 (1984): 245-281. (Engelsk)
Thomas Kormen et al. Algoritmer: Konstruktion og analyse = Introduktion til algoritmer. - 2. udg. - M .: "Williams" , 2006. - S. 1296. - ISBN 0-07-013151-1 .

Links

Union-Find / Kevin Wayne , Pearson-Addison Wesley
Kapitel 22: Datastrukturer for usammenhængende sæt / Introduktion til algoritmer, Thomas H. Cormen, Charles E. Leiserson og Ronald L. Rivest
Visualisering af arbejdet i nogle datastrukturer til ikke-krydsende sæt / ITMO
Implementering af disjoint sæt i C++ Boost Libraries Collection , 2006

Datastrukturer
Lister	array enkelt linket liste dobbelt linket liste Beståelsesliste
Træer	B-træ Binært søgetræ AVL træ Rød-sort træ dynge
Tæller	Instrueret graf rettet acyklisk graf Binært beslutningsdiagram Hypergraf
Andet	Hash bord Stak