algoritmo de kruskal

El algoritmo de Kruskal es un algoritmo de la teoría de grafos para encontrar un árbol recubridor mínimo en un grafo conexo y ponderado. Es decir, busca un subconjunto de aristas que, formando un árbol, incluyen todos los vértices y donde el valor total de todas las aristas del árbol es el mínimo. Si el grafo no es conexo, entonces busca un bosque expandido mínimo (un árbol expandido mínimo para cada componente conexa). El algoritmo de Kruskal es un ejemplo de algoritmo voraz.

se crea un bosque B (un conjunto de árboles), donde cada vértice del grafo es un árbol separadoFunciona de la siguiente manera:

se crea un conjunto C que contenga a todas las aristas del grafo

mientras C es no vacío

eliminar una arista de peso mínimo de C

si esa arista conecta dos árboles diferentes se añade al bosque, combinando los dos árboles en un solo árbol

en caso contrario, se desecha la arista

Al acabar el algoritmo, el bosque tiene un solo componente, el cual forma un árbol de expansión mínimo del grafo.

Carcteristícas

El algoritmo de Kruskal es un ejemplo de algoritmo voraz.

Un ejemplo de árbol expandido mínimo. Cada punto representa un vértice, el cual puede ser un árbol por sí mismo. Se usa el Algoritmo para buscar las distancias más cortas (árbol expandido) que conectan todos los puntos o vértices

jemplo de grafo conexo, no dirigido y con aristas etiquetadas

Cada punto negro es un vértice o nodo, y se le suele asignar una letra para hacer referencia a cada uno. También es posible encontrar grafos donde sus vértices se indican con números, esto no afecta en nada.

"Sea V el conjunto de nodos de un grafo pesado no dirigido. El algoritmo de Prim comienza cuando se asigna a un conjunto U de nodos un nodo inicial perteneciente a V, en el cual crece un árbol de expansión, arista por arista. En cada paso se localiza la arista más corta (u,v) que conecta a U con V-U, y después se agrega v, el vértice en V-U, a U. Este paso se repite hasta que V=U. El algoritmo de Prim es de O(N^2), donde |V| = N."

En otras palabras:

"Este algoritmo construye un árbol agregando aristas de manera iterativa hasta que se obtiene un árbol de expansión mínima. El algoritmo comienza con un solo vértice. Después, en cada iteración, agrega al árbol actual una arista de peso mínimo que no completa un ciclo."

Aplicaciones en la vida real

Este algoritmo puede ser utilizado en muchos campos como lo son las carreteras, vías férreas, aéreas o marítimas. También en redes eléctricas o de telefonía.

Actualmente empresas con servicios de cable e internet que necesitan expandirse lo más posible por toda una ciudad, hacen uso de estos algoritmos para seleccionar las rutas cuyos caminos sean los mas cortos y que generen un ahorro en el uso de cable como la fibra óptica.

ejemplo

En este caso el resultado de encontrar el camino de mínima expansión sería el siguiente:

Un ejemplo simple imaginable sería el querer viajar en auto por carretera a ciertas ciudades y buscar los caminos que generan distancias más cortas entre ciudades, en el menor tiempo posible o viajando la mínima cantidad de horas.

video