Algoritmo kruskal de árbol de expansión mínimo
El algoritmo de Kruskal de árbol de expansión mínimo es el siguiente:
Supongamos que hay un gráfico conectado, el conjunto de todos los vértices en el gráfico es, el conjunto representa el conjunto de vértices que tienen agregado al árbol de expansión, el conjunto representa el conjunto que no se ha agregado al conjunto de vértices en un árbol de expansión.
Al principio se designa aleatoriamente un vértice para ser agregado al conjunto. Luego, cada vez se selecciona la arista con menor peso de entre todas las aristas formadas por el conjunto y los vértices del conjunto como. el borde del árbol de expansión, y El vértice donde está el borde en el conjunto se agrega al conjunto, y así sucesivamente hasta que todos los vértices del conjunto se agregan al conjunto y se obtiene un árbol de expansión mínimo.
El llamado árbol de expansión mínimo significa que en un gráfico conectado ponderado G con N vértices, si hay un subgrafo G', contiene todos los vértices y parte de las aristas en el gráfico G, y no Si se forma un ciclo y la suma de los pesos de los bordes del subgrafo G' es la más pequeña, entonces G' se denomina árbol de expansión mínimo del gráfico G.
El algoritmo se presenta de la siguiente manera:
El algoritmo se refiere a una descripción precisa y completa de la solución del problema. Es una serie de instrucciones claras para resolver el problema. representa un enfoque sistemático. Describe los mecanismos estratégicos para resolver el problema. En otras palabras, es posible obtener el resultado requerido en un tiempo limitado para una determinada especificación de insumo.
Si un algoritmo tiene fallas o es inadecuado para un problema, ejecutarlo no resolverá el problema. Diferentes algoritmos pueden utilizar diferente tiempo, espacio o eficiencia para completar la misma tarea. La calidad de un algoritmo se puede medir por su complejidad espacial y temporal.
Las instrucciones de un algoritmo describen un cálculo que, cuando se ejecuta, puede comenzar desde un estado inicial y una entrada inicial (posiblemente vacía), pasar por una serie limitada y claramente definida de estados y finalmente producir una salida. . y se detiene en un estado final. La transición de un estado a otro no es necesariamente determinista. Algunos algoritmos, incluidos los algoritmos aleatorios, contienen entradas aleatorias.
El concepto de algoritmos formales surgió en parte de los intentos de resolver los problemas de decisión de Hilbert y tomó forma en intentos posteriores de definir computabilidad eficiente o métodos eficientes.
Estos intentos incluyen funciones recursivas propuestas por Kurt Gödel en 1930, Jacques Herbrand y Stephen Cole Crane en 1934 y 1935 respectivamente, y Alonzo Church en El cálculo lambda propuesto en 1936, Formulación1 de Emil Leon Post en 1936, y la máquina de Turing propuesta por Alan Turing en 1937.