A árbol de expansión mínimo (EMT) se define como un árbol de expansión que tenga el peso mínimo entre todos los posibles árboles generadores
A árbol de expansión se define como un subgrafo en forma de árbol de un gráfico conectado y no dirigido que incluye todos los vértices del gráfico. O, para decirlo en palabras de Layman, es un subconjunto de los bordes del gráfico que forma un árbol ( acíclico ) donde cada nodo del gráfico es parte del árbol.
El árbol de expansión mínimo tiene todas las propiedades de un árbol de expansión con la restricción adicional de tener los pesos mínimos posibles entre todos los árboles de expansión posibles. Al igual que un árbol de expansión, también puede haber muchos MST posibles para un gráfico.
Propiedades de un árbol de expansión:
El árbol de expansión sostiene el principios mencionados a continuación :
- El número de vértices ( EN ) en el gráfico y el árbol de expansión es el mismo.
- Hay un número fijo de aristas en el árbol de expansión que es igual a uno menos que el número total de vértices ( Y = V-1 ).
- El árbol de expansión no debe ser desconectado , ya que solo debe haber una única fuente de componente, no más que eso.
- El árbol de expansión debe ser acíclico, cual significa que no habría ningún ciclo en el árbol.
- El costo total (o peso) del árbol de expansión se define como la suma de los pesos de los bordes de todos los bordes del árbol de expansión.
- Puede haber muchos árboles de expansión posibles para un gráfico.
Árbol de expansión mínimo:
A árbol de expansión mínimo (EMT) se define como un árbol de expansión que tenga el peso mínimo entre todos los posibles árboles de expansión.
El árbol de expansión mínimo tiene todas las propiedades de un árbol de expansión con la restricción adicional de tener los pesos mínimos posibles entre todos los árboles de expansión posibles. Al igual que un árbol de expansión, también puede haber muchos MST posibles para un gráfico.
- Veamos el MST del gráfico de ejemplo anterior,
Árbol de expansión mínimo
Algoritmos para encontrar el árbol de expansión mínimo:
Existen varios algoritmos para encontrar el árbol de expansión mínimo a partir de un gráfico determinado, algunos de ellos se enumeran a continuación:
Algoritmo de árbol de expansión mínimo de Kruskal:
Este es uno de los algoritmos populares para encontrar el árbol de expansión mínimo a partir de un gráfico conectado y no dirigido. Esto es un Primero, ordena todos los bordes del gráfico por sus pesos,
Este algoritmo se puede implementar de manera eficiente utilizando una estructura de datos DSU (Disjoint-Set) para realizar un seguimiento de los componentes conectados del gráfico. Esto se utiliza en una variedad de aplicaciones prácticas, como diseño de redes, agrupación en clústeres y análisis de datos.
10 elevado a 6
Sigue el artículo sobre Algoritmo de árbol de expansión mínimo de Kruskal para una mejor comprensión e implementación del algoritmo.
Algoritmo de árbol de expansión mínimo de Prim:
Este también es un algoritmo codicioso. Este algoritmo tiene el siguiente flujo de trabajo:
- Comienza seleccionando un vértice arbitrario y luego agregándolo al MST.
- Luego, verifica repetidamente el peso mínimo del borde que conecta un vértice de MST con otro vértice que aún no está en el MST.
- Este proceso continúa hasta que todos los vértices estén incluidos en el MST.
Para seleccionar de manera eficiente el borde de peso mínimo para cada iteración, este algoritmo utiliza prioridad_queue para almacenar los vértices ordenados por su peso de borde mínimo actualmente. También realiza simultáneamente un seguimiento del MST utilizando una matriz u otra estructura de datos adecuada teniendo en cuenta el tipo de datos que está almacenando.
Este algoritmo se puede utilizar en varios escenarios, como la segmentación de imágenes según el color, la textura u otras características. Para rutas, como encontrar el camino más corto entre dos puntos que debe seguir un camión de reparto.
Sigue el artículo sobre Algoritmo de árbol de expansión mínimo de Prim para una mejor comprensión e implementación de este algoritmo.
Algoritmo de árbol de expansión mínimo de Boruvka:
Este también es un algoritmo de recorrido de gráficos que se utiliza para encontrar el árbol de expansión mínimo de un gráfico no dirigido conectado. Este es uno de los algoritmos más antiguos. El algoritmo funciona construyendo iterativamente el árbol de expansión mínimo, comenzando con cada vértice del gráfico como su propio árbol. En cada iteración, el algoritmo encuentra el borde más barato que conecta un árbol con otro árbol y agrega ese borde al árbol de expansión mínima. Esto es casi similar al algoritmo de Prim para encontrar el árbol de expansión mínimo. El algoritmo tiene el siguiente flujo de trabajo:
- Inicialice un bosque de árboles, con cada vértice del gráfico como su propio árbol.
- Por cada árbol del bosque:
- Encuentra el borde más barato que lo conecta con otro árbol. Agregue estos bordes al árbol de expansión mínima.
- Actualice el bosque fusionando los árboles conectados por los bordes agregados.
- Repita los pasos anteriores hasta que el bosque contenga solo un árbol, que es el árbol de expansión mínima.
El algoritmo se puede implementar utilizando una estructura de datos como una cola de prioridad para encontrar de manera eficiente el borde más barato entre los árboles. El algoritmo de Boruvka es un algoritmo simple y fácil de implementar para encontrar árboles de expansión mínimos, pero puede no ser tan eficiente como otros algoritmos para gráficos grandes con muchas aristas.
Sigue el artículo sobre Algoritmo de árbol de expansión mínimo de Boruvka para una mejor comprensión e implementación de este algoritmo.
apache
Para saber más sobre las propiedades y características del Árbol de expansión mínima, haga clic en aquí.
Aplicaciones de árboles de expansión mínima:
- Diseño de red : Los árboles de expansión se pueden utilizar en el diseño de redes para encontrar el número mínimo de conexiones necesarias para conectar todos los nodos. Los árboles de expansión mínima, en particular, pueden ayudar a minimizar el coste de las conexiones seleccionando los bordes más baratos.
- Procesamiento de imágenes : Los árboles de expansión se pueden utilizar en el procesamiento de imágenes para identificar regiones de intensidad o color similar, lo que puede resultar útil para tareas de segmentación y clasificación.
- Biología : Los árboles de expansión y los árboles de expansión mínima se pueden utilizar en biología para construir árboles filogenéticos que representen las relaciones evolutivas entre especies o genes.
- Análisis de redes sociales : Los árboles de expansión y los árboles de expansión mínima se pueden utilizar en el análisis de redes sociales para identificar conexiones y relaciones importantes entre individuos o grupos.
Algunos problemas populares de entrevistas en MST
| 1. | Encuentre el costo mínimo para conectar todas las ciudades | Práctica |
Algunas preguntas frecuentes sobre árboles de expansión mínima:
1. ¿Puede haber varios árboles de expansión mínima para un gráfico determinado?
Sí, un gráfico puede tener varios árboles de expansión mínima si hay varios conjuntos de aristas con el mismo peso total mínimo.
2. ¿Se pueden utilizar el algoritmo de Kruskal y el algoritmo de Prim para gráficos dirigidos?
No, el algoritmo de Kruskal y el algoritmo de Prim están diseñados únicamente para gráficos no dirigidos.
3. ¿Puede un gráfico desconectado tener un árbol de expansión mínimo?
No, un gráfico desconectado no puede tener un árbol de expansión porque no abarca todos los vértices. Por lo tanto, tampoco puede tener un árbol de expansión mínimo.
4. ¿Se puede encontrar un árbol de expansión mínimo utilizando el algoritmo de Dijkstra?
No, el algoritmo de Dijkstra se utiliza para encontrar el camino más corto entre dos vértices en un gráfico ponderado. No está diseñado para encontrar un árbol de expansión mínimo.
5. ¿Cuál es la complejidad temporal de los algoritmos de Kruskal y Prim?
Tanto el algoritmo de Kruskal como el de Prim tienen una complejidad temporal de O(ElogE) , donde E es el número de aristas del gráfico.