* El blog Cómo el algoritmo de Kruskal usa la unión de conjuntos disjuntos para aplicaciones de la vida real se publicó en el blog HackerEarth *
La mayoría de las compañías de redes de cable utilizan la estructura de datos Disjoint Set Union en el algoritmo de Kruskal para encontrar el camino más corto para tender cables en una ciudad o grupo de ciudades.
Lo que nos lleva a esta publicación sobre las propiedades de Disjoint establece la unión y el árbol de expansión mínimo junto con sus aplicaciones de la vida real.
Antes de continuar con un ejemplo del algoritmo de Kruskal, primero comprendamos qué son los conjuntos disjuntos.
¿Qué son los conjuntos disjuntos?
Un conjunto disjunto es una estructura de datos que realiza un seguimiento de todos los elementos que están separados por una serie de subconjuntos disjuntos (no conectados). Con la ayuda de conjuntos disjuntos, puede realizar un seguimiento de la existencia de elementos en un grupo particular.
Digamos que hay 6 elementos A, B, C, D, E y F. B, C y D están conectados y E y F están emparejados. Esto nos da 3 subconjuntos que tienen elementos (A), (B, C, D) y (E, F).
Los conjuntos disjuntos nos ayudan a determinar rápidamente qué elementos están conectados y cercanos y a unir dos componentes en una sola entidad.
Una estructura de datos de conjunto disjunta consta de dos funciones importantes:
Find () : ayuda a determinar a qué subconjunto pertenece un elemento en particular.
También ayuda a determinar si el elemento está en más de un subconjunto.
Union () : ayuda a verificar si un gráfico es cíclico o no. Y ayuda a conectar o unir dos subconjuntos.
Implementación del conjunto disjunto
Para el ejemplo anterior, suponemos que para el conjunto (B, C, D), B es un nodo padre. Para el conjunto disjunto, mantenemos un representante único para cada nodo.
Si buscamos cualquier elemento en un nodo en particular, nos lleva al padre de ese nodo en particular.
Por lo tanto, cuando busque D, la respuesta sería B.
Del mismo modo, podemos conectar el subconjunto (A) a (E, F), lo que daría como resultado el nodo A como nodo principal.
Ahora tenemos dos subconjuntos, pero B y A no tienen ningún nodo padre. Cada árbol es un conjunto disjunto independiente, es decir, si dos o más elementos están en el mismo árbol, son parte del mismo conjunto disjunto, de lo contrario son independientes.
Entonces, si para un árbol particular B es un representante, entonces Parent [i] = B. Si B no es un representante, podemos mover el árbol hacia arriba para encontrar el padre o representante del árbol.
Puede leer más aquí sobre los conceptos básicos de conjuntos disjuntos.
Algoritmo de Kruskal
El árbol de expansión es la suma de los pesos de todos los bordes de un árbol. Un árbol de expansión mínimo (MST) es uno que cuesta menos entre todos los árboles de expansión.
Aquí hay un ejemplo de un árbol de expansión mínimo.
El algoritmo de Kruskal y el algoritmo de Prim son dos algoritmos populares para encontrar los árboles de expansión mínima.
El algoritmo de Kruskal utiliza el enfoque codicioso para encontrar un árbol de expansión mínimo. El algoritmo de Kruskal trata cada nodo como un árbol independiente y se conecta uno con otro solo si tiene el costo más bajo en comparación con todas las demás opciones disponibles.
Pasos del algoritmo de Kruskal:
- Ordene los bordes del gráfico con respecto a sus pesos.
- Comience a agregar bordes al MST desde el borde con el menor peso hasta el borde del mayor peso.
- Solo agregue bordes que no formen un ciclo, bordes que conectan solo componentes desconectados.
O como una explicación más simple,
Paso 1 – Eliminar todos los bucles y bordes paralelos
Paso 2 – Organice todos los bordes en orden ascendente de costo
Paso 3: agregue bordes con el menor peso
Pero, ¿cómo verifica si dos vértices están conectados o no? Ahí es donde entra en uso la aplicación real de Disjoint Sets.
El algoritmo de Kruskal explicado con un ejemplo.
Estoy seguro de que muy pocos de ustedes estarían trabajando para una compañía de redes de cable, así que hagamos que el problema del algoritmo de Kruskal sea más fácil de identificar.
En su viaje a Venecia, planea visitar todos los sitios importantes del patrimonio mundial, pero tiene poco tiempo. Para que su itinerario funcione, decide utilizar el algoritmo de Kruskal utilizando conjuntos disjuntos.
Aquí hay un mapa de Venecia.
Simplifiquemos el mapa convirtiéndolo en un gráfico como se muestra a continuación y nombrando ubicaciones importantes en el mapa con letras y distancia en metros (x 100).
Comprendamos cómo se usa el algoritmo de Kruskal en aplicaciones del mundo real usando el mapa anterior.
Paso 1- Eliminar todos los bucles y bordes paralelos
Entonces, para el mapa dado, tenemos un borde paralelo que corre entre Madonna dell’Orto (D) y la Basílica de San Marcos (J), que tiene una longitud de 2.4kms (2400mts). Eliminaremos la carretera paralela y conservaremos la longitud de 1.8 km (1800 m) para la representación.
Paso 2 – Organice todos los bordes en el gráfico en orden ascendente. El algoritmo de Kruskal considera a cada grupo como un árbol y aplica conjuntos disjuntos para verificar cuántos de los vértices son parte de otros árboles.
Paso 3: agregue bordes con el menor peso; comenzamos con los bordes con menor peso / costo. Por lo tanto, B, C se conecta primero considerando su costo de borde solo 1
I, J ha costado 1; Es el borde conectado a continuación.
Luego, conectamos los bordes con peso = 2.
Del mismo modo, conectamos el nodo K, L que tiene una arista con peso = 3.
Como se indica en la tabla anterior, todos los bordes están conectados en orden ascendente, asegurando que no se forme un bucle o ciclo entre 2 vértices.
Esto nos da el siguiente gráfico, que es el árbol de expansión mínimo para el problema dado.
Después de comprender cómo funciona el algoritmo de Kruskal, es importante comprender la diferencia entre MST y TSP.
Problema de árbol de expansión mínimo vs. vendedor ambulante
Un árbol de expansión mínimo lo ayuda a construir un árbol que conecta todos los nodos, o como en el caso anterior, todos los lugares / ciudades con un peso total mínimo. Mientras que un problema de vendedor ambulante (TSP) requiere que visite todos los lugares mientras regresa a su nodo inicial con un peso total mínimo.
Las siguientes son algunas de las otras aplicaciones de la vida real del algoritmo de Kruskal:
- Cables de aterrizaje
- Red de televisión
- Operaciones de tour
Puede encontrar el código C ++ para el algoritmo de Kruskal: aquí
