Union Find Algorithm

UNION FIND ALGORITHM
YURANI TUQUERRES ANDRADE
UNIVERSIDAD DEL CAUCA

FACULTAD DE INGENIERIA ELECTRONICA Y TELECOMUNICACIONES
PROGRAMA INGENIERIA ELECTRONICA Y TELECOMUNICACIONES
POPAYAN - CAUCA
2023
YURANI TUQUERRES ANDRADE
CONSULTA
WEYMAR ANDRES ASTAIZA SULEZ
UNIVERSIDAD DEL CAUCA

FACULTAD DE INGENIERIA ELECTRONICA Y TELECOMUNICACIONES
PROGRAMA INGENIERIA ELECTRONICA Y TELECOMUNICACIONES
POPAYAN - CAUCA
2023
INTRODUCCION
El algoritmo Union-Find, también conocido como estructura de datos

Disjoint-Set, es una poderosa herramienta utilizada en muchas áreas de
la informática, incluida la teoría de grafos, la optimización y la visión por
computadora. El algoritmo nos permite mantener eficientemente una
partición de un conjunto en subconjuntos disjuntos y realizar
operaciones como fusionar dos subconjuntos o encontrar el
subconjunto al que pertenece un elemento.
En este trabajo, exploraremos el algoritmo Union-Find, sus propiedades

y sus diversas aplicaciones en informática. Comenzaremos con una
breve introducción al algoritmo y luego profundizaremos en su
implementación, complejidad y casos de uso. A través de ejemplos y
fragmentos de código, demostraremos cómo se puede aplicar el
algoritmo Union-Find para resolver una amplia gama de problemas en
informática.
Un algoritmo de búsqueda de unión es un algoritmo que realiza dos

operaciones útiles en una estructura de datos:
• Buscar: determina en qué subconjunto se encuentra el

elemento que buscamos. Esto se puede usar para determinar
si dos elementos están en el mismo subconjunto.
• Unión: une dos subconjuntos en un solo subconjunto. Aquí
primero tenemos que verificar si los dos subconjuntos
pertenecen al mismo conjunto. Si no, entonces no podemos
realizar la unión.
• El conjunto disjunto, es un grupo de conjuntos donde ningún

elemento puede estar en más de un conjunto. Admite otra
operación importante llamada MakeSet, que crea un conjunto
que contiene solo un elemento.
• Make- set crea un nuevo conjunto cuyo único miembro (y por lo

tanto representante) es x Dado que los conjuntos son disjuntos,
requerimos que x no esté ya en algún otro lugar.
Este algoritmo funciona, de tal manera que podemos determinar si dos

elementos están en el mismo subconjunto comparando el resultado de
dos operaciones. Si los dos elementos están en el mismo conjunto,
tienen la misma representación; de lo contrario, pertenecen a
conjuntos diferentes. Si se llama a la unión de dos elementos, fusiona
los dos subconjuntos a los que pertenecen los dos elementos.
Hay varias implementaciones diferentes del algoritmo Union-Find, pero

una de las más comunes es la implementación de "unión por rango y
compresión de camino". En esta implementación, los componentes
conectados se representan como árboles, y los vértices se representan
como nodos en estos árboles. La operación de unión se realiza uniendo
los dos árboles más pequeños, mientras que la operación de búsqueda
se realiza al buscar el nodo raíz de cada árbol y comparar si son iguales.
En el caso de la unión por tamaño, un nodo almacena su tamaño, que

es simplemente su número de descendientes (incluido el propio
nodo). Cuando los árboles con raíces x e y se fusionan, el nodo con
más descendientes se convierte en el padre. Si los dos nodos tienen el
mismo número de descendientes, cualquiera de ellos puede convertirse
en el padre. En ambos casos, el tamaño del nuevo nodo principal se
establece en su nuevo número total de descendientes.
Path compression: En este tipo de búsqueda, se comprime el camino

de la raíz a un nodo durante la búsqueda. Esto ayuda a reducir la altura
del árbol y a mejorar la eficiencia de las operaciones de unión y
búsqueda.
Weighted union with path compression: Este es el tipo más común de

unión en el algoritmo Union-Find. Combina las técnicas de union by size
y path compression para lograr un equilibrio óptimo entre la eficiencia y
la complejidad del algoritmo. Cada implementación de Union-Find
puede utilizar uno o más de estos tipos de uniones para ajustarse mejor
a las necesidades de la aplicación específica.
El algoritmo Union-Find es ampliamente utilizado en algoritmos de

grafos y estructuras de datos, y tiene muchas aplicaciones prácticas,
como la detección de componentes conectados en redes sociales y la
detección de ciclos en grafos.
El algoritmo mantiene una estructura de datos para representar los

componentes conectados, utilizando las operaciones principales:
"unión" y "búsqueda". La operación de unión combina componentes
posteriores conectados en un solo componente, pero la operación de
búsqueda determina si los vértices posteriores están conectados en el
mismo componente.
Algunos ejemplos donde podemos utilizar el algoritmo Union Find, son:
• Detección de ciclos en un grafo: En un grafo no dirigido, el

algoritmo Union-Find puede utilizarse para detectar si hay ciclos
en el grafo. Si unión entre dos nodos ya está en el mismo conjunto,
eso significa que un camino existe entre ellos, y por lo tanto, se
encontró un ciclo.
• Componentes conexas: El algoritmo Union-Find puede utilizarse
para encontrar todas las componentes conexas en un grafo no
dirigido. Se puede comenzar con un conjunto por separado para
cada vértice del grafo. Luego, para cada borde en el grafo, se
unen los conjuntos que corresponden a los vértices extremos del
borde. Al final, todos los vértices que están en el mismo conjunto
pertenecen a la misma componente conexa.
• Árboles de expansión mínima: El algoritmo Kruskal utiliza el
algoritmo Union-Find para construir un árbol de expansión mínima
en un grafo no dirigido. El proceso comienza con un conjunto por
separado para cada vértice del grafo, luego se ordenan todos los
bordes por peso y se procesan en orden ascendente. Para cada
borde, se une el conjunto que corresponde a un vértice al conjunto
que corresponde al otro vértice.
• Seguimiento de grupos: El algoritmo Union-Find puede ser
utilizado para seguimiento de grupos en una matriz. Por ejemplo,
se puede utilizar para encontrar grupos de celdas adyacentes que
contienen el mismo valor.
EJEMPLO DE SOLUCION
Tenemos un numero de conjuntos que queremos administrar en

conjuntos disjuntos, donde ningún elemento puede estar en más de un
conjunto, por lo que cada elemento puede pertenecer a un solo
conjunto: por ejemplo, tenemos cinco conjuntos
disjuntos S1 , S2 , S3 , S4 , y S5 representado por un árbol, como se
muestra en el siguiente diagrama. Cada conjunto contiene inicialmente
solo un elemento cada uno, por lo que su puntero principal apunta a sí
mismo o NULL .
S1 = {1}, S2 = {2}, S3 = {3}, S4 = {4} and S5 = {5}

los Find operación en el elemento i regresará representante de S i,
dónde 1 <= i <= 5 , es decir, Find (i) = i .
Sí lo hacemos Unión (S3, S4) , S3 y S4 se fusionarán en un conjunto

inconexo, S3 . Ahora,
S1 = {1}, S2 = {2}, S3 = {3, 4} and S5 = {5} .
Find (4) regresará representante del conjunto S3 , es decir, Find (4) = 3
Si lo hacemos Unión (S1, S2) , S1 y S2 se fusionarán en un conjunto
S1 = {1, 2}, S3 = {3, 4} and S5 = {5} .
Find (2) o Find (1) devolverá el representante del conjunto S1 , es decir, Find (2)
= Find (1) = 1
Si lo hacemos Unión (S3, S1) , S3 y S1 se fusionarán en un conjunto

S3 = {1, 2, 3, 4} and S5 = {5} .

Union Find Algorithm

Cargado por

Copyright:

Formatos disponibles

Union Find Algorithm

Cargado por

Información del documento

Título original

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Union Find Algorithm

Cargado por

Copyright:

Formatos disponibles

UNION FIND ALGORITHM

YURANI TUQUERRES ANDRADE

UNIVERSIDAD DEL CAUCA

YURANI TUQUERRES ANDRADE

WEYMAR ANDRES ASTAIZA SULEZ

UNIVERSIDAD DEL CAUCA

El algoritmo Union-Find, también conocido como estructura de datos

En este trabajo, exploraremos el algoritmo Union-Find, sus propiedades

Un algoritmo de búsqueda de unión es un algoritmo que realiza dos

• Buscar: determina en qué subconjunto se encuentra el

• El conjunto disjunto, es un grupo de conjuntos donde ningún

• Make- set crea un nuevo conjunto cuyo único miembro (y por lo

Este algoritmo funciona, de tal manera que podemos determinar si dos

Hay varias implementaciones diferentes del algoritmo Union-Find, pero

En el caso de la unión por tamaño, un nodo almacena su tamaño, que

Path compression: En este tipo de búsqueda, se comprime el camino

Weighted union with path compression: Este es el tipo más común de

El algoritmo Union-Find es ampliamente utilizado en algoritmos de

El algoritmo mantiene una estructura de datos para representar los

• Detección de ciclos en un grafo: En un grafo no dirigido, el

Tenemos un numero de conjuntos que queremos administrar en

S1 = {1}, S2 = {2}, S3 = {3}, S4 = {4} and S5 = {5}

Sí lo hacemos Unión (S3, S4) , S3 y S4 se fusionarán en un conjunto

Si lo hacemos Unión (S3, S1) , S3 y S1 se fusionarán en un conjunto

También podría gustarte