Si está buscando una analogía de la vida real, le diría que imagine gotas de agua en una ventana cuando llueve. (Estoy seguro de que lo has visto antes). Cada vez que dos gotas se acercan, colapsan en una sola gota de agua. Esa es la unión de union-find.
De todos modos, esto es lo que realmente es union-find. Tienes un montón de nodos y todos están agrupados, así:
Ahora, puede preguntar si dos nodos están en el mismo grupo, por lo que podría preguntar, “¿están los nodos amarillo y negro en el mismo grupo?” y vuelve “¡apuesto!”
- ¿Cuáles son algunos de los buenos libros sobre Algoritmos de aprendizaje automático de árbol de decisión?
- Como estudiante de primer año de una sucursal que no es CS en un IIT, ¿cómo domino las estructuras de datos, los algoritmos y el aprendizaje automático por mi cuenta?
- ¿Avanzar en CS en general hará que los algoritmos sean cada vez más complejos con el tiempo que las personas no pueden manejar? ¿Cuáles son las soluciones para ese caso?
- ¿Qué algoritmos usa Bing para clasificar los resultados de búsqueda? ¿La patente de Google les impide usar PageRank? Análisis de enlaces en general?
- ¿Qué debo hacer si tengo dificultades con la programación dinámica en SPOJ?
Ahora, también se nos permite realizar una fusión o unión en dos componentes, como este:
Tenga en cuenta que la operación sindical es irreversible; la estructura de datos union-find no permite dividir un componente nuevamente.
Entonces, ahora que he descrito lo que hace, ¿cómo implementamos realmente el algoritmo de búsqueda de unión? Básicamente, en cada componente tenemos un árbol como este:
Cada nodo almacena un puntero a otro nodo. Sin embargo, cada componente tiene exactamente un nodo sin puntero: esta es la raíz de ese componente. Aquí, las raíces son los nodos rojo, azul y rosa.
Para hacer una fusión, solo agregamos una flecha más, como esta:
Ahora el nodo azul es la raíz del componente más grande; El nodo rojo ya no es una raíz.
¡Bueno! Ahora, como dijimos anteriormente, el objetivo de esta estructura de datos es saber si dos nodos están en el mismo componente. Para hacer esto, presentamos la operación de búsqueda , que toma un nodo y solo sigue las flechas y devuelve la raíz de su componente. Entonces, si ejecutamos find (amarillo), trazará el camino amarillo -> rojo -> azul y regresará azul. Si ejecutamos find (verde), solo trazará verde -> azul y devolverá azul. ¡Entonces sabemos que el amarillo y el verde están en el mismo componente!
Sin embargo, para muchos nodos, esto es ineficiente. ¡Los caminos pueden alargarse mucho! Entonces, ¿cómo soluciona union-find esto? Hace dos optimizaciones:
- Compresión de ruta: cuando ejecutamos find en un nodo, rastreamos una ruta de nodos que sabemos que están en este componente. También podríamos mover todos sus punteros para apuntar al nodo raíz mientras estamos en él; luego ejecutar find en esos nodos en el futuro será súper rápido. (Hasta que ocurran más fusiones, de todos modos).
- Fusionar por rango : cuando fusionamos dos árboles, es mejor hacer que el árbol más corto sea hijo del árbol más grande. Para esto, tenemos que hacer un seguimiento de las profundidades de los árboles, pero eso no es gran cosa.
Implemente estos dos, y union-find se ejecutará en [math] O (\ alpha (n)) [/ math] amortizado por operación. Aquí, [math] \ alpha [/ math] es el inverso de la función de Ackermann, que es de crecimiento extremadamente lento.
Terminaré con una aplicación, ya que de lo contrario podría pensar que el único punto de unión es cuando necesita modelar puntos bonitos en burbujas como en las imágenes de arriba.
El algoritmo de Kruskal es un algoritmo para encontrar el árbol de mínima expansión de un gráfico. Empiezas separando todos los vértices. Luego, recorre los bordes de menor a mayor peso. Usted elige el borde para agregar a su árbol de expansión a menos que esos vértices estén conectados por una ruta de bordes que ya ha elegido.
Para implementar esto, necesita una forma de determinar si dos nodos están en el mismo componente conectado; ¡esto es exactamente lo que hace la estructura de datos union-find! Cada vez que elige una nueva ventaja para su árbol de expansión, une los dos componentes que conecta. (Tenga en cuenta, sin embargo, que el árbol de expansión que construye y los árboles que usa en la estructura de datos de búsqueda de unión no tendrán conexión, aparte de dividir los vértices en componentes conectados de la misma manera).
