Algoritmos para la búsqueda de Árboles Generadores Mínimos: Prim y Kruskal

Un árbol generador de un grafo G, es un subgrafo que es árbol y contiene a todos los vértices del grafo.

Un árbol generador mínimo en un grafo conexo y ponderado G, es un árbol generador de G de peso mínimo.

Se presentan a continuación dos métodos para construir un árbol generador mínimo de un grafo conexo y ponderado de 'n' vértices.

Algoritmo de Prim (1957) (Jarník, 1930)

Algoritmo de Kruskal (1956)

Victorino Sanz Prat (980079)
Facultad de Informática. UPM