Árbol de expansión mínima python

Queremos encontrar un subárbol de este grafo que conecte todos los vértices (es decir, que sea un árbol de expansión) y que tenga el menor peso (es decir, que la suma de pesos de todas las aristas sea mínima) de todos los árboles de expansión posibles.

El algoritmo de Kruskal coloca inicialmente todos los nodos del grafo original aislados entre sí, para formar un bosque de árboles de un solo nodo, y luego va fusionando gradualmente estos árboles, combinando en cada iteración dos cualquiera de todos los árboles con alguna arista del grafo original. Antes de la ejecución del algoritmo, todas las aristas se ordenan por peso (en orden no decreciente). A continuación, comienza el proceso de unificación: se eligen todas las aristas desde la primera hasta la última (en orden ordenado), y si los extremos de la arista elegida actualmente pertenecen a subárboles diferentes, estos subárboles se combinan, y la arista se añade a la respuesta. Después de iterar por todas las aristas, todos los vértices pertenecerán al mismo subárbol, y obtendremos la respuesta.

Porque si no, habría dos componentes que podrían estar conectados con al menos una arista. Aunque esto es imposible, porque Kruskal habría elegido una de estas aristas, ya que los ids de los componentes son diferentes.

Algoritmo de Prim

La forma más común de averiguarlo es un algoritmo llamado Union FInd. El algoritmo Union-Find divide los vértices en clústeres y nos permite comprobar si dos vértices pertenecen al mismo clúster o no y, por tanto, decidir si añadir una arista crea un ciclo.

El algoritmo de Prim es otro popular algoritmo de árbol de extensión mínima que utiliza una lógica diferente para encontrar el MST de un gráfico. En lugar de empezar por una arista, el algoritmo de Prim empieza por un vértice y sigue añadiendo aristas de menor peso que no están en el árbol, hasta que se han cubierto todos los vértices.

Pseudocódigo del algoritmo de Prim

El algoritmo de Kruskal es el concepto que se introduce en la teoría de grafos de la matemática discreta. Se utiliza para descubrir el camino más corto entre dos puntos en un grafo ponderado conectado. Este algoritmo convierte un grafo dado en un bosque, considerando cada nodo como un árbol independiente. Estos árboles sólo pueden enlazarse entre sí si la arista que los conecta tiene un valor bajo y no genera un ciclo en la estructura MST. En este tutorial, aprenderá más sobre el Algoritmo de Kruskal en detalle.

Como se mencionó anteriormente, el algoritmo de Kruskal se utiliza para generar un árbol de tramo mínimo para un gráfico dado. Pero, ¿qué es exactamente un árbol de extensión mínima? Un árbol de extensión mínima es un subconjunto de un grafo con el mismo número de vértices que el grafo y aristas iguales al número de vértices -1. También tiene un coste mínimo para la suma de todos los pesos de las aristas en un árbol de expansión.

El algoritmo de Kruskal ordena todas las aristas en orden creciente de sus pesos de arista y sigue añadiendo nodos al árbol sólo si la arista elegida no forma ningún ciclo. Además, elige la arista con un coste mínimo al principio y la arista con un coste máximo al final. Por lo tanto, se puede decir que el algoritmo de Kruskal hace una elección localmente óptima, con la intención de encontrar la solución global óptima. Por eso se le llama algoritmo codicioso.

Algoritmo de Kruskal en línea

Introducción al Algoritmo de KruskalSupongamos que hay algunos pueblos en una ciudad, usted siendo el alcalde de la ciudad quiere visitar todos los pueblos pero tiene muy poco tiempo para ello. Así que le interesará visitar los pueblos de tal manera que la distancia total recorrida por usted durante la visita sea la mínima posible. El algoritmo de Kurskal le ayudará en este caso, ya que se utiliza para encontrar el árbol de expansión mínimo (MST) de cualquier grafo no dirigido, ponderado y conectado. Antes de hablar de los detalles del algoritmo de Kruskal, veamos qué se entiende por árbol de expansión mínima de un grafo: un árbol de expansión es un subgrafo de un grafo conexo no dirigido que es un árbol y que incluye todos los vértices. Por lo tanto, un árbol de expansión mínima correspondería a un árbol de expansión con el peso mínimo. El peso de un árbol de expansión es la suma del peso de las aristas presentes en él.