Weighted Quick-Union con el algoritmo de Compresión de ruta

Question

Hay un algoritmo "Unión rápida ponderada con compresión de ruta".

el código:

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

Preguntas:

1. ¿Cómo funciona la compresión de caminos? id[i] = id[id[i]] significa que llegamos solo al segundo ancestro de nuestro nodo, no a la raíz.

2. iz[] contiene números enteros de 0 a N-1. ¿Cómo nos ayuda iz[] la cantidad de elementos en el conjunto?

¿Alguien me puede aclarar esto?

Answer 1

Primero entiendo que id es un bosque . id[i] es el padre de i. Si id[i] == i significa que i es una raíz.

Por alguna raíz i (donde id[i] == i) entonces iz[i] es el número de elementos en el árbol raíz en 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; 
} 

¿Cómo funciona la compresión de caminos? id[i] = id[id[i]] significa que llegamos solo al segundo ancestro de nuestro nodo, no a la raíz.

Como estamos ascendiendo el árbol para encontrar la raíz, pasamos los nodos de sus padres a sus abuelos. Esto aplana parcialmente el árbol. Observe que esta operación no cambia de qué árbol es miembro el nodo, esto es todo lo que nos interesa. Esta es la técnica de compresión de ruta.

(Usted se dio cuenta el derecho de bucle? while(i == id[i]) termina una vez i es un nodo raíz)

iz[] contiene números enteros de 0 a N-1. ¿Cómo nos ayuda iz[] la cantidad de elementos en el conjunto?

Hay un error de transcripción en el código:

Esta es la versión correcta:

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

iz[i] es el número de elementos de un árbol con raíz en i (o si i no es una raíz, entonces iz[i] no está definido). Por lo tanto, debe inicializarse en 1, no en i. Inicialmente, cada elemento es un árbol "singleton" separado del tamaño 1.

Answer 2

Pregunta 1. No es correcto decir que la línea id [i] = id [id [i]]; solo llega al segundo ancestro de la raíz. Te darás cuenta de que while loop while (i! = id [i]) se detiene solo cuando el nodo i apunta a la raíz, es decir, cuando i == id [i]. Por esta vez, debe haber señalado el nodo a la raíz usando la línea id [i] = id [id [i]]; donde el id interno [i] es la raíz.

Pregunta 2.

Se equivoca al inicializar iz [i] = i; en realidad debería ser iz [i] = 1; lo que significa que todos y cada uno de los nodos se inicializan en 1 al principio, ya que son del tamaño 1. En la función de unión, se da cuenta de que tenemos las líneas iz [j] + = iz [i]; y iz [i] + = iz [j]; que actualiza el tamaño del nodo raíz para que sea la suma de los tamaños de los dos componentes unidos. Esto actualiza de manera eficiente los tamaños de los nodos.

Answer 3

id [i] = id [id [i]]; // esta línea representa "compresión de ruta"

El código anterior es "variante simple de una pasada" como se menciona en la diapositiva de Union Find (Algoritmos, Parte I de Kevin Wayne y Robert Sedgewick). Por lo tanto, su conjetura para la pregunta 1 es correcta. Cada nodo examinado apunta a su abuelo.

para hacer que cada puntos de nodo examinados a la raíz necesitaremos aplicación de dos pasos:

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

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

Answer 4

Una cosa más que señalar aquí:

Si bien la búsqueda la raíz cuando estamos haciendo id[i]=id[id[i]] ie; haciéndolo bajo su gran padre

-entonces el tamaño de id[i] disminuirá por tamaño de i, e; iz[id[i]]-=iz[i]

Ahora esto hace que el código sea perfectamente correcto.

No estoy seguro de esto, pero intuitivamente me siento, Su ausencia no causa problemas porque siempre estamos comparando el tamaño de las raíces.