Ważony Quick-Union z algorytmem kompresji ścieżki

Question

Istnieje algorytm "Weighted Quick-Union with Path Compression".

kodu:

public class WeightedQU 
{ 
    private int[] id; 
    private int[] iz; 

    public WeightedQU(int N) 
    { 
     id = new int[N]; 
     iz = new int[N]; 
     for(int i = 0; i < id.length; i++) 
     { 
      iz[i] = i; 
      id[i] = i; 
     } 
    } 

    public int root(int i) 
    { 
     while(i != id[i]) 
     { 
      id[i] = id[id[i]]; // this line represents "path compression" 
      i = id[i]; 
     } 
     return i; 
    } 

    public boolean connected(int p, int q) 
    { 
     return root(p) == root(q); 
    } 

    public void union(int p, int q) // here iz[] is used to "weighting" 
    { 
     int i = root(p); 
     int j = root(q); 
     if(iz[i] < iz[j]) 
     { 
      id[i] = j; 
      iz[j] += iz[i]; 
     } 
     else 
     { 
      id[j] = i; 
      iz[i] += iz[j]; 
     } 
    } 
} 

Pytania:

1. Jak działa kompresji ścieżki? id[i] = id[id[i]] oznacza, że ​​docieramy tylko do drugiego ancestera naszego węzła, a nie do korzenia.

2. iz[] zawiera liczby całkowite od 0 do N-1. W jaki sposób iz[] pomaga nam poznać liczbę elementów w zestawie?

Czy ktoś może mi to wyjaśnić?

Answer 1

Najpierw zrozum, że id to las. id[i] jest rodzicem i. Jeśli id[i] == i oznacza to, że i jest rootem.

jakiegoś pierwiastka i (gdzie id[i] == i), a następnie iz[i] jest wiele elementów w drzewa zakorzenione w i.

public int root(int i) 
{ 
    while(i != id[i]) 
    { 
     id[i] = id[id[i]]; // this line represents "path compression" 
     i = id[i]; 
    } 
    return i; 
} 

Jak działa kompresji ścieżki? id[i] = id[id[i]] oznacza, że ​​docieramy tylko do drugiego ancestera naszego węzła, a nie do korzenia.

Kiedy wspinamy się po drzewie, aby znaleźć korzeń, przenosimy węzły z ich rodziców do dziadków. To częściowo spłaszcza drzewo. Zauważ, że ta operacja nie zmienia drzewa, którego węzeł jest członkiem, to wszystko, co nas interesuje. To jest technika kompresji ścieżki.

(You zauważyłem prawo pętli? while(i == id[i]) kończy raz i to węzeł główny)

iz[] zawiera liczby całkowite od 0 do N-1. W jaki sposób iz[] pomaga nam poznać liczbę elementów w zestawie?

Jest to błąd transkrypcji w kodzie:

Jest to poprawna wersja:

for(int i = 0; i < id.length; i++) 
{ 
    iz[i] = 1; // RIGHT 
    id[i] = i; 
} 

iz[i] jest liczba elementów drzewem zakorzenionym w i (lub jeśli i nie jest rootem, a następnie iz[i] jest niezdefiniowane). Powinien więc zostać zainicjowany na 1, a nie na i. Początkowo każdy element jest oddzielnym drzewem "singleton" o rozmiarze 1.

Answer 2

Pytanie 1. Nie można powiedzieć, że id linii [i] = id [id [i]]; dociera tylko do drugiego przodka korzenia. Zdasz sobie sprawę, że podczas gdy pętla while (i! = id [i]) zatrzymuje się tylko wtedy, gdy węzeł i wskazuje na element główny, tj. gdy i == id [i] .Kiedy tym razem wskaże węzeł do katalogu głównego za pomocą id linii [i] = id [id [i]]; gdzie wewnętrznym id [i] jest root.

Pytanie 2.

Mylisz się zainicjować Iz [i] = i; w rzeczywistości powinno być iz [i] = 1; co oznacza, że ​​każdy rozmiar węzła jest początkowo inicjalizowany przez 1, ponieważ są one wielkości 1. W funkcji związanej zdajesz sobie sprawę, że mamy linie iz [j] + = iz [i]; i iz [i] + = iz [j]; która aktualizuje rozmiar węzła głównego jako sumę rozmiarów połączonych ze sobą dwóch składników. Skutecznie aktualizuje rozmiary węzłów.

Answer 3

id [i] = id [id [i]]; // ta linia reprezentuje "kompresję ścieżki"

Powyższy kod jest "Prostszy wariant jednoprzebiegowy", jak wspomniano na slajdzie Wyszukiwania Unii (Algorithms, Part I, Kevin Wayne and Robert Sedgewick). Dlatego twoje przypuszczenie na pytanie 1 jest poprawne. Każdy badany węzeł wskazuje na jego dziadka.

aby każdy badane punkty węzła do korzenia będziemy potrzebować realizację dwóch pass:

/** 
* Returns the component identifier for the component containing site <tt>p</tt>. 
* @param p the integer representing one site 
* @return the component identifier for the component containing site <tt>p</tt> 
* @throws java.lang.IndexOutOfBoundsException unless 0 <= p < N 
*/ 
public int find(int p) { 
    int root = p; 
    while (root != id[root]) 
     root = id[root]; 
    while (p != root) { 
     int newp = id[p]; 
     id[p] = root; 
     p = newp; 
    } 
    return root; 
} 

referencyjny: http://algs4.cs.princeton.edu/15uf/WeightedQuickUnionPathCompressionUF.java.html

Answer 4

jeszcze jedno należy zauważyć:

Przy poszukiwaniu root, kiedy robimy id[i]=id[id[i]] tj .; czyniąc pod swoim wielkim rodzicem

- wtedy rozmiar zmniejszy się o wielkość i i, e; iz[id[i]]-=iz[i]

To powoduje, że kod jest całkowicie poprawny.

Nie jestem tego pewien, ale intuicyjnie czuję, Jego nieobecność nie powoduje problemów, ponieważ zawsze porównujemy rozmiar korzeni.