Primero, veamos dos imágenes de compresión de ruta:
Union-Find Sets es una estructura de datos muy delicada y práctica, que se utiliza principalmente para lidiar con el problema de fusión de algunos conjuntos sin intervención. Algunos usos comunes incluyen la conexión de subgrafos, algoritmos de Kruskal para encontrar el árbol de expansión mínimo y los antepasados menos comunes (LCA).
Al usar y buscar un conjunto, primero habrá un conjunto de conjuntos dinámicos disjuntos s = {s 1, s 2, ⋯, s k}, que generalmente usa un entero para representar un elemento en el conjunto.
Cada conjunto puede contener uno o más elementos, y un elemento en el conjunto se selecciona como representante. No es importante cuidar qué elementos están contenidos en cada conjunto, y no es importante cuidar qué elemento se selecciona como representante. Lo que nos importa es que para un elemento dado, podemos encontrar rápidamente el conjunto (representación) donde se encuentra este elemento, y fusionar los conjuntos donde se encuentran los dos elementos, y la complejidad del tiempo de estas operaciones es constante.
Hay tres operaciones básicas para verificar y colección:
Madeet (s): cree un conjunto nuevo y de búsqueda, que contiene s conjuntos de elementos individuales.
Unión (x, y): fusiona los conjuntos donde se encuentran el elemento x y el elemento y, y requiere que los conjuntos donde se encuentran x e y no se cruzan, y si se cruzan, no se fusionan.
encontrar (x): encuentre el representante del conjunto donde se encuentra el elemento x. Esta operación también se puede utilizar para determinar si dos elementos están en el mismo conjunto. Simplemente compare sus respectivos representantes.
paquete com.datestructure.union_find; // Nuestra quinta edición Union-FindPublic Class UnionFind5 {// rank [i] representa el número de capas del árbol representadas por un conjunto arraigado por i // en el código posterior, no mantendremos la semántica de rango, es decir, el valor del rango del rango puede no ser el valor de la capa del árbol durante la compresión de la ruta. Es solo un estándar para comparar el rango privado int []; Private int [] padre; // El padre [i] representa el nodo principal apuntado por el elemento i-them privado int count; // Número de datos // constructor public unionfind5 (int count) {rank = new int [count]; parent = new int [Count]; this.count = Count; // Inicialización, cada padre [i] apunta a sí mismo, lo que indica que cada elemento forma su propio conjunto para (int i = 0; i <count; i ++) {parent [i] = i; rango [i] = 1; }} // proceso de búsqueda, busque el número de establecimiento correspondiente al elemento p // o (h) complejidad, h es la altura del árbol privado int find (int p) {afirmar (p> = 0 && p <count); // Compresión de ruta 1 mientras (p! = parent [p]) {parent [p] = parent [parent [p]]; p = padre [p]; } return p; // Compresión de ruta 2, algoritmo recursivo // if (p! = parent [p]) // parent [p] = find (parent [p]); // return parent [p]; } // verifique si el elemento P y el elemento Q pertenecen a un conjunto // o (h) complejidad, h es la altura del árbol público booleano ISconnected (int p, int q) {return find (p) == find (q); } // fusionar el conjunto al que el elemento p y el elemento q pertenecen // o (h) complejidad, h es la altura del árbol public void unioneLements (int p, int q) {int proot = find (p); int qroot = find (q); if (proot == qroot) return; // juzga la dirección de fusión basada en el número diferente de elementos en el árbol donde se encuentran los dos elementos // fusionar un conjunto con menos elementos en un conjunto con más elementos if (rank [proot] <rank [qroot]) {parent [proot] = qroot; } else if (rank [qroot] <rank [proot]) {parent [qroot] = proot; } else {// rank [proot] == rank [qroot] parent [proot] = qroot; rango [qroot] += 1; // En este momento, mantengo el valor de rango}}}Resumir
Lo anterior es toda la explicación detallada del código de compresión de ruta en este artículo sobre la implementación y la recopilación de la programación Java. Espero que sea útil para todos. Los amigos interesados pueden continuar referiéndose a otros temas relacionados en este sitio. Si hay alguna deficiencia, deje un mensaje para señalarlo. ¡Gracias amigos por su apoyo para este sitio!