Rozłączna struktura danych - Disjoint-set data structure

MakeSet tworzy 8 singletonów.

Po wykonaniu niektórych operacji Unionniektóre zestawy są grupowane razem.

W informatyce , A struktura zbiorów rozłącznych , zwany również unia zdobycia struktura danych lub zestaw seryjnej zdobycia , to struktura danych, która przechowuje zbiór rozłącznych (nie pokrywających) sety. Równoważnie przechowuje podział zbioru na rozłączne podzbiory. Zapewnia operacje dodawania nowych zestawów, scalania zestawów (zastępowania ich przez ich sumę ) i znajdowania reprezentatywnego członka zestawu. Ostatnia operacja pozwala sprawnie zorientować się, czy jakieś dwa elementy znajdują się w tym samym lub różnych zestawach.

Chociaż istnieje kilka sposobów implementacji rozłącznych struktur danych, w praktyce często są one utożsamiane z konkretną implementacją zwaną lasem o rozłącznym zestawie . Jest to wyspecjalizowany rodzaj lasu, który wykonuje zjednoczenia i znajduje się w niemal stałym, zamortyzowanym czasie. Wykonanie sekwencji m dodawania, łączenia lub znajdowania na rozłącznym lesie z n węzłami wymaga całkowitego czasu O ( m α( n )) , gdzie α( n ) jest niezwykle wolno rosnącą odwrotną funkcją Ackermanna . Lasy rozłączne nie gwarantują tej wydajności na podstawie operacji. Pojedyncze operacje łączenia i znajdowania mogą trwać dłużej niż czas stały razy α( n ) , ale każda operacja powoduje, że las zestawu rozłącznego dostosowuje się, aby kolejne operacje były szybsze. Lasy rozłączne są zarówno asymptotycznie optymalne, jak i praktycznie efektywne.

Struktury danych o zbiorze rozłącznym odgrywają kluczową rolę w algorytmie Kruskala do znajdowania minimalnego drzewa opinającego grafu. Znaczenie minimalnych drzew rozpinających oznacza, że ​​rozłączne struktury danych leżą u podstaw szerokiej gamy algorytmów. Ponadto rozłączne struktury danych mają również zastosowanie do obliczeń symbolicznych, a także w kompilatorach, zwłaszcza w przypadku problemów z alokacją rejestrów .

Historia

Rozłączne osadzone lasy zostały po raz pierwszy opisane przez Bernard A. Galler i Michaela J. Fischera w 1964. W 1973, czas ich złożoność była ograniczona do , na powtórzyć logarytm o , o Hopcroft i Ullmana . W 1975 r. Robert Tarjan jako pierwszy udowodnił ( odwrotną funkcję Ackermanna ) górną granicę złożoności czasowej algorytmu, aw 1979 r. wykazał, że jest to dolna granica dla przypadku ograniczonego. W 1989 roku Fredman i Saks wykazali, że (zamortyzowane) słowa muszą być dostępne dla każdej rozłącznej struktury danych na operację, udowadniając w ten sposób optymalność struktury danych. ${\ Displaystyle O (\ log ^ {*} (n))}$${\ Displaystyle n}$${\ Displaystyle O (m \ alfa (n))}$${\ Displaystyle \ Omega (\ alfa (n))}$

W 1991 roku Galil i Italiano opublikowali przegląd struktur danych dla zbiorów rozłącznych.

W 1994 r. Richard J. Anderson i Heather Woll opisali zrównoległą wersję Union-Find, która nigdy nie musi się blokować.

W 2007 roku Sylvain Conchon i Jean-Christophe Filliâtre opracowali trwałą wersję rozłącznej struktury danych leśnych, co pozwala na efektywne zachowanie poprzednich wersji struktury i sformalizowanie jej poprawności za pomocą asystenta weryfikacji Coq . Jednak implementacja jest asymptotyczna tylko wtedy, gdy jest używana efemerycznie lub jeśli ta sama wersja struktury jest używana wielokrotnie z ograniczonym nawrotem.

Reprezentacja

Każdy węzeł w rozłącznym lesie składa się ze wskaźnika i pewnych informacji pomocniczych, rozmiaru lub rangi (ale nie obu). Wskaźniki są używane do tworzenia nadrzędnych drzew wskaźników , w których każdy węzeł, który nie jest korzeniem drzewa, wskazuje na jego rodzica. Aby odróżnić węzły główne od innych, ich wskaźniki nadrzędne mają nieprawidłowe wartości, takie jak cykliczne odwołanie do węzła lub wartość wartownika. Każde drzewo reprezentuje zestaw przechowywany w lesie, przy czym członkowie zestawu są węzłami w drzewie. Węzły główne zapewniają reprezentantów zbioru: Dwa węzły znajdują się w tym samym zbiorze wtedy i tylko wtedy, gdy korzenie drzew zawierających węzły są równe.

Węzły w lesie można przechowywać w dowolny sposób wygodny dla aplikacji, ale powszechną techniką jest przechowywanie ich w tablicy. W takim przypadku rodzice mogą być wskazani przez ich indeks tablicy. Każdy wpis tablicy wymaga Θ(lg n ) bitów pamięci dla wskaźnika rodzica. Dla reszty wpisu wymagana jest porównywalna lub mniejsza ilość pamięci, więc liczba bitów wymaganych do przechowania lasu wynosi Θ( n lg n ) . Jeśli implementacja używa węzłów o stałym rozmiarze (ograniczając w ten sposób maksymalny rozmiar lasu, który może być przechowywany), wymagana pamięć ma charakter liniowy w n .

Operacje

Struktury danych o rozłącznym zbiorze obsługują trzy operacje: Tworzenie nowego zbioru zawierającego nowy element; Znalezienie reprezentanta zbioru zawierającego dany element; i Łączenie dwóch zestawów.

Tworzenie nowych zestawów

MakeSetOperacja dodaje nowy element. Ten element jest umieszczany w nowym zestawie zawierającym tylko nowy element, a nowy zestaw jest dodawany do struktury danych. Jeśli struktura danych jest zamiast tego postrzegana jako partycja zestawu, wówczas MakeSetoperacja powiększa zestaw poprzez dodanie nowego elementu i rozszerza istniejącą partycję, umieszczając nowy element w nowym podzbiorze zawierającym tylko nowy element.

W lesie o zestawie rozłącznym MakeSetinicjuje wskaźnik nadrzędny węzła oraz rozmiar lub rangę węzła. Jeśli korzeń jest reprezentowany przez węzeł, który wskazuje na siebie, to dodanie elementu można opisać za pomocą następującego pseudokodu:

function MakeSet(x) is
    if x is not already in the forest then
        x.parent := x
        x.size := 1     // if nodes store size
        x.rank := 0     // if nodes store rank
    end if
end function

Ta operacja ma stałą złożoność czasową. W szczególności inicjowanie rozłącznego lasu z n węzłami wymaga czasu O ( n ) .

W praktyce MakeSetmusi być poprzedzona operacją przydzielającą pamięć do przechowywania x . Dopóki alokacja pamięci jest amortyzowaną operacją w czasie stałym, tak jak w przypadku dobrej implementacji tablicy dynamicznej , nie zmienia to asymptotycznej wydajności lasu o losowym zestawie.

Znalezienie przedstawicieli zestawu

FindOperacji następuje łańcuch wskaźników macierzystych z określonym węzłem zapytania X , aż do osiągnięcia elementu głównego. Ten element główny reprezentuje zbiór, do którego należy x i może być samym x . Findzwraca element główny, do którego dociera.

Wykonywanie Findoperacji stwarza ważną okazję do ulepszenia lasu. Czas w Findoperacji jest spędzany na ściganiu wskaźników nadrzędnych, więc bardziej płaskie drzewo prowadzi do szybszych Findoperacji. Kiedy a Findjest wykonywane, nie ma szybszego sposobu dotarcia do korzenia niż podążanie za każdym wskaźnikiem nadrzędnym po kolei. Jednak wskaźniki nadrzędne odwiedzone podczas tego wyszukiwania można zaktualizować, aby wskazywały bliżej korzenia. Ponieważ każdy element odwiedzany w drodze do katalogu głównego jest częścią tego samego zestawu, nie zmienia to zestawów przechowywanych w lesie. Przyspiesza to jednak przyszłe Findoperacje, nie tylko na węzłach między węzłem zapytania a korzeniem, ale także na ich potomkach. Ta aktualizacja jest ważną częścią gwarancji wydajności zamortyzowanego lasu rozłącznego.

Istnieje kilka algorytmów, Findktóre pozwalają osiągnąć asymptotycznie optymalną złożoność czasową. Jedna rodzina algorytmów, znana jako kompresja ścieżki , sprawia, że ​​każdy węzeł między węzłem zapytania a punktem głównym jest korzeniem. Kompresja ścieżki może być zaimplementowana za pomocą prostej rekurencji w następujący sposób:

function Find(x) is
    if x.parent ≠ x then
        x.parent := Find(x.parent)
        return x.parent
    else
        return x
    end if
end function

Ta implementacja wykonuje dwa przejścia, jedno w górę drzewa i drugie w dół. Wymaga wystarczającej ilości pamięci do przechowywania ścieżki od węzła zapytania do korzenia (w powyższym pseudokodzie ścieżka jest niejawnie reprezentowana przy użyciu stosu wywołań). Można to zmniejszyć do stałej ilości pamięci, wykonując oba przejścia w tym samym kierunku. Implementacja pamięci stałej przechodzi od węzła zapytania do korzenia dwukrotnie, raz w celu znalezienia korzenia i raz w celu zaktualizowania wskaźników:

function Find(x) is
    root := x
    while root.parent ≠ root do
        root := root.parent
    end while

    while x.parent ≠ root do
        parent := x.parent
        x.parent := root
        x := parent
    end while

    return root
end function

Tarjan i Van Leeuwen opracowali również Findalgorytmy jednoprzebiegowe , które zachowują tę samą złożoność najgorszego przypadku, ale są bardziej wydajne w praktyce. Nazywa się to dzieleniem ścieżki i dzieleniem ścieżki na pół. Oba te aktualizują wskaźniki nadrzędne węzłów na ścieżce między węzłem zapytania a korzeniem. Podział ścieżki zastępuje każdy wskaźnik nadrzędny na tej ścieżce wskaźnikiem do dziadka węzła:

function Find(x) is
    while x.parent ≠ x do
        (x, x.parent) := (x.parent, x.parent.parent)
    end while
    return x
end function

Dzielenie ścieżki na pół działa podobnie, ale zastępuje tylko co drugi wskaźnik nadrzędny:

function Find(x) is
    while x.parent ≠ x do
        x.parent := x.parent.parent
        x := x.parent
    end while
    return x
end function

Łączenie dwóch zestawów

Operacja zastępuje zestaw zawierający x i zestaw zawierający y ich sumą. pierwszy używa do określenia korzeni drzew zawierających x i y . Jeśli korzenie są takie same, nie ma nic więcej do zrobienia. W przeciwnym razie oba drzewa muszą zostać połączone. Odbywa się to poprzez ustawienie wskaźnika rodzica x na y lub ustawienie wskaźnika rodzica y na x . Union(x, y)UnionFind

Wybór, który węzeł staje się rodzicem, ma wpływ na złożoność przyszłych operacji na drzewie. Jeśli robi się to niedbale, drzewa mogą stać się zbyt wysokie. Załóżmy na przykład, że Uniondrzewo zawierające x jest zawsze poddrzewem drzewa zawierającego y . Zacznij od lasu, który właśnie został zainicjowany z elementami i wykonaj , , ..., . Powstały las zawiera jedno drzewo, którego korzeniem jest n , a ścieżka od 1 do n przechodzi przez każdy węzeł w drzewie. Dla tego lasu czas biegu to O ( n ) . ${\displaystyle 1,2,3,\ldots,n,}$Union(1, 2)Union(2, 3)Union(n - 1, n)Find(1)

W wydajnej implementacji wysokość drzewa jest kontrolowana za pomocą sumy według rozmiaru lub sumy według rangi . Oba wymagają, aby węzeł przechowywał informacje poza wskaźnikiem nadrzędnym. Te informacje są używane do decydowania, który korzeń zostanie nowym rodzicem. Obie strategie zapewniają, że drzewa nie staną się zbyt głębokie.

W przypadku łączenia według rozmiaru węzeł przechowuje swój rozmiar, który jest po prostu liczbą potomków (łącznie z samym węzłem). Kiedy drzewa o korzeniach x i y zostaną połączone, węzeł z większą liczbą potomków staje się rodzicem. Jeśli dwa węzły mają taką samą liczbę potomków, każdy z nich może zostać rodzicem. W obu przypadkach rozmiar nowego węzła nadrzędnego jest ustawiony na jego nową całkowitą liczbę potomków.

function Union(x, y) is
    // Replace nodes by roots
    x := Find(x)
    y := Find(y)

    if x = y then
        return  // x and y are already in the same set
    end if

    // If necessary, rename variables to ensure that
    // x has at least as many descendants as y
    if x.size < y.size then
        (x, y) := (y, x)
    end if

    // Make x the new root
    y.parent := x
    // Update the size of x
    x.size := x.size + y.size
end function

Liczba bitów potrzebnych do przechowania rozmiaru jest oczywiście liczbą bitów potrzebnych do przechowania n . Dodaje to stały czynnik do wymaganej pamięci lasu.

W przypadku sumowania według rangi węzeł przechowuje swoją rangę , która jest górną granicą jego wysokości. Gdy węzeł jest inicjowany, jego ranga jest ustawiana na zero. Aby scalić drzewa o korzeniach x i y , najpierw porównaj ich rangi. Jeśli rangi są różne, to większe drzewo rang staje się rodzicem, a rangi x i y nie zmieniają się. Jeśli rangi są takie same, to każdy z nich może zostać rodzicem, ale ranga nowego rodzica jest zwiększana o jeden. Chociaż ranga węzła jest wyraźnie powiązana z jego wysokością, przechowywanie rang jest bardziej wydajne niż przechowywanie wysokości. Wysokość węzła może się zmieniać podczas Findoperacji, więc przechowywanie rang pozwala uniknąć dodatkowego wysiłku związanego z utrzymaniem prawidłowej wysokości. W pseudokodzie związek według rangi to:

function Union(x, y) is
    // Replace nodes by roots
    x := Find(x)
    y := Find(y)

    if x = y then
        return  // x and y are already in the same set
    end if

    // If necessary, rename variables to ensure that
    // x has rank at least as large as that of y
    if x.rank < y.rank then
        (x, y) := (y, x)
    end if

    // Make x the new root
    y.parent := x
    // If necessary, increment the rank of x
    if x.rank = y.rank then
        x.rank := x.rank + 1
    end if
end function

Można pokazać, że każdy węzeł ma rangę lub mniejszą. W konsekwencji ranga może być przechowywana w bitach O (log log n ) , co czyni go asymptotycznie pomijalną częścią rozmiaru lasu. ${\displaystyle \lpodłoga \lg n\rpodłoga}$

Z powyższych implementacji jasno wynika, że ​​rozmiar i ranga węzła nie mają znaczenia, chyba że węzeł jest korzeniem drzewa. Gdy węzeł staje się dzieckiem, jego rozmiar i ranga nie są już więcej dostępne.

Złożoność czasu

Implementacja lasu rozłącznego, w której Findnie aktualizuje wskaźników nadrzędnych i Unionnie próbuje kontrolować wysokości drzewa, może mieć drzewa o wysokości O ( n ) . W takiej sytuacji operacje Findi Unionwymagają czasu O ( n ) .

Jeśli implementacja używa samej kompresji ścieżki, to sekwencja n MakeSet operacji, po których następuje do n -1 Union operacji i f Find operacji, ma najgorszy czas działania . ${\ Displaystyle \ Theta (n + f \ cdot \ lewo (1 + \ log _ {2 + f / n} n \ prawo))}$

Korzystanie unii według rangi, ale bez aktualizacji wskaźników dominujących podczas Find, daje czas pracy dla m operacji dowolnego typu, aż do n , którego są operacje. ${\ Displaystyle \ Theta (m \ log n)}$MakeSet

Kombinacja kompresji ścieżki, dzielenia lub dzielenia na pół, z sumowaniem według rozmiaru lub według rangi, skraca czas wykonywania m operacji dowolnego typu, z których do n jest MakeSetoperacjami, do . To sprawia, że amortyzowany czas trwania każdej operacji . Jest to asymptotycznie optymalne, co oznacza, że ​​każda rozłączna struktura danych musi wykorzystywać zamortyzowany czas na operację. Tutaj funkcja jest odwrotną funkcją Ackermanna . Odwrotna funkcja Ackermanna rośnie niezwykle wolno, więc współczynnik ten wynosi 4 lub mniej dla każdego n, które faktycznie można zapisać w fizycznym wszechświecie. To sprawia, że ​​operacje rozłączne są praktycznie amortyzowane przez stały czas. ${\ Displaystyle \ Theta (m \ alfa (n))}$${\ Displaystyle \ Theta (\ alfa (n))}$${\ Displaystyle \ Omega (\ alfa (n))}$${\ Displaystyle \ alfa (n)}$

Dowód złożoności czasowej O(log*(n)) Union-Find

Dokładna analiza wydajności rozłącznego lasu jest nieco skomplikowana. Istnieje jednak znacznie prostsza analiza, która udowadnia, że ​​zamortyzowany czas dla dowolnego m Find lub Unionoperacji na rozłącznym lesie zawierającym n obiektów wynosi O (mlog ^* n ) , gdzie log ^* oznacza iterowany logarytm .

Lemat 1: Ponieważ funkcja wyszukiwania podąża ścieżką do korzenia, rośnie ranga napotkanego węzła.

Dowód: twierdzenie, że skoro operacje Znajdź i Połącz są stosowane do zbioru danych, fakt ten pozostaje prawdą z biegiem czasu. Początkowo, gdy każdy węzeł jest korzeniem własnego drzewa, jest to trywialnie prawdziwe. Jedynym przypadkiem, w którym można zmienić rangę węzła, jest zastosowanie operacji Union by Rank . W takim przypadku drzewo o niższej randze zostanie dołączone do drzewa o wyższej randze, a nie odwrotnie. A podczas operacji find wszystkie węzły odwiedzone na ścieżce zostaną dołączone do korzenia, który ma wyższą rangę niż jego dzieci, więc i ta operacja nie zmieni tego faktu.

Lemat 2: Węzeł u będący korzeniem poddrzewa z rangą r ma przynajmniej węzły. ${\ Displaystyle 2 ^ {r}}$

Dowód: Początkowo, gdy każdy węzeł jest korzeniem własnego drzewa, jest to trywialnie prawdziwe. Załóżmy, że węzeł u z rangą r ma co najmniej 2 ^r węzłów. Następnie, gdy dwa drzewa o randze r zostaną połączone za pomocą operacji Union by Rank , powstanie drzewo o randze r +1 , którego korzeń ma przynajmniej węzły.${\ Displaystyle 2 ^ {r} + 2 ^ {r} = 2 ^ {r + 1}}$

Lemat 3: Maksymalna liczba węzłów rangi r wynosi co najwyżej${\ Displaystyle {\ Frac {n} {2 ^ {r}}}.}$

Dowód: Z lematu 2 wiemy, że węzeł u będący korzeniem poddrzewa o randze r ma przynajmniej węzły. Maksymalną liczbę węzłów o randze r otrzymamy, gdy każdy węzeł o randze r jest korzeniem drzewa, które ma dokładnie węzły. W tym przypadku liczba węzłów rangi r wynosi${\ Displaystyle 2 ^ {r}}$${\ Displaystyle 2 ^ {r}}$${\ Displaystyle {\ Frac {n} {2 ^ {r}}}.}$

Dla wygody definiujemy tutaj „wiadro”: wiadro to zbiór, który zawiera wierzchołki o określonych rangach.

Tworzymy kilka wiader i indukcyjnie wkładamy wierzchołki do wiader zgodnie z ich rangami. Oznacza to, że wierzchołki z rangą 0 trafiają do wiadra zerowego, wierzchołki z rangą 1 do pierwszego wiadra, wierzchołki z rangą 2 i 3 do drugiego wiadra. Jeśli B- ^ty kubełek zawiera wierzchołki z rangami z przedziału, to (B+1)-szy kubełek będzie zawierał wierzchołki z rangami z przedziału${\ Displaystyle \ lewo [r, 2 ^ {r} -1 \ po prawej] = [r, R-1]}$${\ Displaystyle \ lewo [R, 2 ^ {R} -1 \ po prawej].}$

Dowód znalezienia związku${\ Displaystyle O (\ log ^ {*} n)}$

Możemy poczynić dwie obserwacje dotyczące wiader.

1. Całkowita liczba kubełków wynosi co najwyżej log ^* n

   Dowód: Kiedy przechodzimy z jednego wiadra do drugiego, dodajemy jeszcze jedno dwa do mocy, czyli następne wiadro będzie${\ Displaystyle \ lewo [B, 2 ^ {B} -1 \ po prawej]}$${\ Displaystyle \ lewo [2 ^ {B}, 2 ^ {2 ^ {B}} -1 \ po prawej]}$

2. Maksymalna liczba elementów w kubełku to najwyżej${\ Displaystyle \ lewo [B, 2 ^ {B} -1 \ po prawej]}$${\ Displaystyle {\ Frac {2n} {2 ^ {B}}}}$

   Dowód: Maksymalna liczba elementów w wiadrze to najwyżej${\ Displaystyle \ lewo [B, 2 ^ {B} -1 \ po prawej]}$${\ Displaystyle {\ Frac {n} {2 ^ {B}}} + {\ Frac {n} {2 ^ {B + 1}}} + {\ Frac {n} {2 ^ {B + 2}} }+\cdots +{\frac {n}{2^{2^{B}-1}}}\leq {\frac {2n}{2^{B}}}.}$

Niech F reprezentuje listę wykonanych operacji "znajdź" i niech

$${\ Displaystyle T_ {1} = \ suma _ {F} {\ tekst {(link do katalogu głównego)}}}$$

$${\displaystyle T_{2}=\suma _{F}{\text{(liczba łączy, przez które przechodzi się w przypadku różnych wiader)}}}$$

$${\displaystyle T_{3}=\suma _{F}{\text{(liczba łączy przebytych w miejscach, gdzie wiadra są takie same).}}}$$

Wtedy całkowity koszt m znalezisk wynosi${\displaystyle T=T_{1}+T_{2}+T_{3}.}$

Ponieważ każda operacja find wykonuje dokładnie jedno przejście prowadzące do pierwiastka, mamy T ₁ = O ( m ) .

Również z powyższego ograniczenia liczby wiader mamy T ₂ = O ( m log ^* n ) .

Dla T ₃ załóżmy, że przechodzimy przez krawędź od u do v , gdzie u i v mają rangę w wiadrze [ B , 2 ^B − 1] , a v nie jest pierwiastkiem (w czasie tego przechodzenia, w przeciwnym razie należy uwzględnić w T ₁ ). Napraw u i rozważ sekwencję, która pełni rolę v w różnych operacjach wyszukiwania. Ze względu na kompresję ścieżki i nieuwzględnianie krawędzi do pierwiastka sekwencja ta zawiera tylko różne węzły, a dzięki Lematowi 1 wiemy, że szeregi węzłów w tej sekwencji ściśle rosną. Z tego, że oba węzły znajdują się w wiaderku, możemy wywnioskować, że długość k ciągu (liczba razy, gdy węzeł u jest dołączony do innego pierwiastka w tym samym wiaderku) jest co najwyżej liczbą rang w wiaderkach B , że jest co najwyżej${\displaystyle v_{1},v_{2},\ldots,v_{k}}$${\ Displaystyle 2 ^ {B} -1-B <2 ^ {B}.}$

W związku z tym, ${\ Displaystyle T_ {3} \ leq \ suma _ {[B, 2 ^ {B} 1]} \ suma _ {u} 2 ^ {B}.}$

Z uwag 1 i 2 możemy wywnioskować, że${\ Displaystyle T_ {3} \ równoważnik \ suma _ {B} 2 ^ {B} {\ Frac {2n} {2 ^ {B}}} \ równoważnik 2n \ log ^ {*} n.}$

W związku z tym, ${\ Displaystyle T = T_ {1} + T_ {2} + T_ {3} = O (m \ log ^ {*} n).}$

Aplikacje

Demo dla Union-Find przy użyciu algorytmu Kruskala do znalezienia minimalnego drzewa opinającego.

Struktury danych rozłączne osadzone model podziału zbioru , na przykład śledzić połączonych składników o o nieukierunkowane wykresie . Model ten można następnie wykorzystać do określenia, czy dwa wierzchołki należą do tego samego komponentu, czy też dodanie krawędzi między nimi spowoduje powstanie cyklu. Algorytm Union-Find jest używany w wysokowydajnych implementacjach unifikacji .

Ta struktura danych jest używana przez bibliotekę wykresów Boost do implementacji funkcji Incremental Connected Components . Jest to również kluczowy element implementacji algorytmu Kruskala w celu znalezienia minimalnego drzewa rozpinającego grafu.

Należy zauważyć, że implementacja jako rozłączne lasy nie pozwala na usuwanie krawędzi, nawet bez kompresji ścieżki lub heurystyki rang.

Sharir i Agarwal donoszą o powiązaniach między najgorszym przypadkiem zachowania zbiorów rozłącznych a długością sekwencji Davenporta-Schinzla , struktury kombinatorycznej z geometrii obliczeniowej.

Zobacz też

• Udokładnianie partycji , inna struktura danych do utrzymywania rozłącznych zestawów, z aktualizacjami, które rozdzielają zestawy, a nie łączą je ze sobą
• Łączność dynamiczna

Bibliografia

Zewnętrzne linki

• Implementacja C++ , część bibliotek Boost C++
• Implementacja Java z aplikacją do segmentacji obrazów w kolorze, Statistical Region Merging (SRM), IEEE Trans. Wzór Analny. Macha Intel. 26(11): 1452-1458 (2004)
• Aplet Java: Implementacja Graphical Union-Find , Rory LP McGuire
• Implementacja Matlaba, która jest częścią Biblioteki Komponentów Tracker
• Implementacja Pythona
• Objaśnienie wizualne i kod C#