Algoritmo kruskal
Páginas: 2 (476 palabras)
Publicado: 19 de noviembre de 2011
ALGORITMO 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 aristasque, 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 árbolexpandido mínimo para cada componente conexa). 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.
Funciona de la siguiente manera:
se crea un bosque B (unconjunto de árboles), donde cada vértice del grafo es un árbol separado
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 Csi 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 solocomponente, el cual forma un árbol de expansión mínimo del grafo.
Este algoritmo fue publicado por primera vez en Proceedings of the American Mathematical Society, pp. 48–50 en 1956, y fue escrito porJoseph Kruskal.
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 (árbolexpandido) que conectan todos los puntos o vértices. |
EJEMPLO DE EL ALGORITMO KRUSKAL
// Declaraciones en el archivo .h
int cn; //cantidad de nodosvector< vector > ady; //matriz de adyacencia
// Devuelve la matriz de adyacencia del arbol minimo.
vector< vector > Grafo :: 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 aristasque, 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 árbolexpandido mínimo para cada componente conexa). 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.
Funciona de la siguiente manera:
se crea un bosque B (unconjunto de árboles), donde cada vértice del grafo es un árbol separado
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 Csi 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 solocomponente, el cual forma un árbol de expansión mínimo del grafo.
Este algoritmo fue publicado por primera vez en Proceedings of the American Mathematical Society, pp. 48–50 en 1956, y fue escrito porJoseph Kruskal.
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 (árbolexpandido) que conectan todos los puntos o vértices. |
EJEMPLO DE EL ALGORITMO KRUSKAL
// Declaraciones en el archivo .h
int cn; //cantidad de nodosvector< vector > ady; //matriz de adyacencia
// Devuelve la matriz de adyacencia del arbol minimo.
vector< vector > Grafo :: kruskal(){...
Leer documento completo
Regístrate para leer el documento completo.