Weighted Quick-Union mit Pfadkomprimierungsalgorithmus

Question

Es gibt einen Algorithmus "gewichtete Quick-Union mit Pfadkomprimierung".

Der Code:

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]; 
     } 
    } 
} 

Fragen:

1. Wie funktioniert der Weg Komprimierung? id[i] = id[id[i]] bedeutet, dass wir nur den zweiten Vorfahren unseres Knotens erreichen, nicht die Wurzel.

2. iz[] enthält Ganzzahlen von 0 bis N-1. Wie hilft uns iz[] die Anzahl der Elemente im Set wissen?

Kann jemand dies für mich klären?

Answer 1

Zuerst verstehen, dass id ein Wald ist. id[i] ist das übergeordnete Element von i. Wenn id[i] == i bedeutet dies, dass i ein Root ist.

Für einige root i (wo id[i] == i), dann ist iz[i] die Anzahl der Elemente in dem Baum bei i verwurzelt.

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

Wie funktioniert der Weg Komprimierung? id[i] = id[id[i]] bedeutet, dass wir nur den zweiten Vorfahren unseres Knotens erreichen, nicht die Wurzel.

Während wir den Baum aufsteigen, um die Wurzel zu finden, bewegen wir Knoten von ihren Eltern zu ihren Großeltern. Dies flacht den Baum teilweise ab. Beachten Sie, dass diese Operation nicht die Struktur ändert, in der der Knoten Mitglied ist. Das ist alles, was uns interessiert. Dies ist die Pfadkomprimierungstechnik.

(Sie haben die Schleife rechts bemerkt? while(i == id[i]) endet, sobald i ein Wurzelknoten ist)

iz[] ganze Zahlen von 0 bis N-1 enthält. Wie hilft uns iz[] die Anzahl der Elemente im Set wissen?

Es ist ein Transkriptionsfehler in dem Code:

Dies ist die korrekte Version:

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

iz[i] ist die Anzahl der Elemente für einen Baum an i verwurzelt (oder wenn i ist keine Wurzel, dann ist iz[i] nicht definiert). Daher sollte es auf 1, nicht i initialisiert werden. Anfangs ist jedes Element ein separater "Singleton" Baum der Größe 1.

Answer 2

Frage 1. Es ist nicht richtig zu sagen, dass die Zeile id [i] = id [id [i]]; erreicht nur den zweiten Vorfahren der Wurzel. Sie werden erkennen, dass die while-Schleife while (i! = id [i]) nur dann stoppt, wenn der Knoten i auf die Wurzel zeigt, dh wenn i == id [i] soll den Knoten mit der Zeile id auf die Wurzel gelenkt haben [id] = id [id [i]]; wo die innere ID [i] die Wurzel ist.

Frage 2.

Sie sind falsch iz zu initialisieren [i] = i; eigentlich sollte es iz [i] = 1 sein; Das bedeutet, dass jede Knotengröße zu Beginn mit 1 initialisiert wird, da sie die Größe 1 haben. In der Vereinigungsfunktion erkennen Sie, dass wir die Zeilen iz [j] + = iz [i] haben; und iz [i] + = iz [j]; Dadurch wird die Größe des Stammknotens auf die Summe der Größen der beiden miteinander verbundenen Komponenten aktualisiert. Dies aktualisiert effizient die Knotengrößen.

Answer 3

id [i] = id [id [i]]; // Diese Zeile steht für "path compression"

Der obige Code ist "Simplere One-Pass-Variante" wie in der Folie von Union Find (Algorithmen, Teil I von Kevin Wayne und Robert Sedgewick) erwähnt. Daher ist Ihre Schätzung für Frage 1 richtig. Jeder untersuchte Knoten zeigt auf seinen Großelternteil.

zu jedem untersuchten Knotenpunkte an der Wurzel machen wir zwei Pass Implementierung benötigen:

/** 
* 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; 
} 

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

Answer 4

Eine weitere Sache, hier anzumerken:

Während der Suche nach die Wurzel, wenn wir machen id[i]=id[id[i]] dh; ich mache es unter seinem großen Elternteil

-dann wird die Größe von id[i] um die Größe von i i, e; iz[id[i]]-=iz[i]

Jetzt macht dies den Code vollkommen korrekt.

Ich bin mir nicht sicher, aber intuitiv fühle ich, Seine Abwesenheit verursacht keine Probleme, weil wir immer die Größe der Wurzeln vergleichen.