algoritmo

Algoritmo de Kruskal

Este es un algoritmo del tipo "avaro" ("greedy"). Comienza inicialmente con un grafo que contiene sólo los nodos del grafo original, sin arcos. Luego, en cada iteración, se agrega al grafo el arco más barato que no introduzca un ciclo. El proceso termina cuando el grafo está completamente conectado. En general, la estrategia "avara" no garantiza que se encuentre un óptimoglobal, porque es un método "miope", que sólo optimiza las decisiones de corto plazo. Por otra parte, a menudo este tipo de métodos proveen buenas heurísticas, que se acercan al óptimo global.
En este caso, afortunadamente, se puede demostrar que el método "avaro" logra siempre encontrar el óptimo global, por lo cual un árbol cobertor encontrado por esta vía está garantizado que es un árbolcobertor mínimo.
Una forma de ver este algoritmo es diciendo que al principio cada nodo constituye su propia componente conexa, aislado de todos los demás nodos.
Durante el proceso de construcción del árbol, se agrega un arco sólo si sus dos extremos se encuentran en componentes conexas distintas, y luego de agregarlo esas dos componentes conexas se fusionan en una sola.

Descripción del AlgoritmoEntrada: Un grafo G con costos, conexo.
Idea: Mantener un subgrafo acíclico cobertor H de modo que en cada paso exista al menos un árbol de cobertura de costo mínimo T, tal que H sea subgrafo de T. Considérense las aristas de G ordenadas por costo en forma no decreciente, los empates se rompen arbitrariamente.
Inicialización: E(H) = Ø
Iteración: Si la siguiente arista e de G (en el ordendado) une dos componentes de H, entonces agregamos e a E(H). Si no, la ignoramos.
Terminación: Termínese el algoritmo cuando H sea conexo o cuando se acaben las aristas de G.
Función Kruskal (G = : grafo; longitud: A → R+): conjunto de aristas
{Iniciación}
Ordenar A por longitudes crecientes
n ← el número de nodos que hay en N
T ← ∅ {contendrá las aristas del árbol de recubrimiento mínimo}Iniciar n conjuntos, cada uno de los cuales contiene un elemento distinto de N {bucle greedy }
Repetir
e ← {u, v} ← arista más corta aún no considerada
compu ← buscar(u)
compv ← buscar(v)
si compu ≠ compv entonces
fusionar(compu, compv)
T ← T ∪ {e}
hasta que T contenga n - 1 aristas
devolver T



Complejidad del Algoritmo

El algoritmo requiere que las |E| aristas estén ordenadaspreviamente. Esto toma O(|E| log(|E|)) operaciones.
El proceso de examinar las |E| aristas toma a lo más O(|E|) iteraciones; de ellas, n-1 requieren actualizar la lista de componentes a las que pertenecen los n vértices. Esto puede ser hecho en un total de O(nlog2n) operaciones, o incluso en forma más astuta en O(nα (n)), donde:





Ejemplo:






Algoritmo de Prim

La característicaprincipal del algoritmo de Kruskal es que éste selecciona las mejores aristas sin preocuparse de las conexiones con las aristas seleccionadas antes. El resultado es una proliferación de árboles que eventualmente se juntan para formar un árbol.

Ya que sabemos que al final tenemos que producir un solo árbol, por qué no intentar hacer como que el árbol crezca naturalmente hasta la obtención de unárbol generador mínimo? Así, la próxima arista seleccionada sería siempre una que se conecta al árbol que ya existe.

Esa es la idea del algoritmo de Prim. Se caracteriza por hacer la selección en forma local, partiendo de un nodo seleccionado y construyendo el árbol en forma ordenada.
Dado que el arco es seleccionado de aquellos que parten del árbol ya construido, la viabilidad está asegurada.También se puede demostrar que el algoritmo de Prim es correcto, es decir, que devuelve un árbol de recubrimiento minimal en todos los casos.
Al inicio el conjunto B contiene un vértice arbitrario. En cada paso, el algoritmo considera todas las aristas que tocan a B y selecciona a la de menor peso. Después, el algoritmo aumenta en B el vértice ligado por esa arista que no estaba en B. El...