Algoritmo De Prim

UNIVERSIDAD DE EL SALVADOR
FACULTAD DE INGENIERIA Y ARQUITECTURA
ESCUELA DE INGENIERIA DE SISTEMAS INFORMATICOS
ESTRUCTURA DE DATOS
ALGORITMOS DE PRIM Y KRUSKAL

El objetivo del algoritmo dePrim es que dado el grafo no dirigido G, encontrar el árbol de expansión
de costo mínimo asociado al grafo dado, denotado por A. Si todos los vértices de G están en A
entonces G es conexo.
Un árbolde expansión es un subgrafo de G con su mismo número de nodos pero que es un árbol. Es
conectado y sin ciclos.
Dado el grafo G (no dirigido):

Su árbol de expansión de costo mínimo A asociado es:2

3

2

3
5

A1

8

A1
3

3

5
2

2
4

5

5

4

4
3

3
Notar que:

4

1. Es conectado y sin ciclos
2. Posee n vértices y n-1 aristas
3. Si se añade unaarista, entonces resulta un ciclo
(Observar líneas punteadas)

Dado G = (V,A), con V={1,2,…} asignar U={1}. Esto es asignar a U el vértice inicial del grafo G y paso
a paso se va añadiendo en cadaiteración otro vértice de V-U tal que si u es un vértice de U, la arista
(u,v) es la más corta/barata entre u en U y v en V-U.
El proceso termina cuando V=U (todos los vértices de V están en U) y se haformado A que es el
mínimo porque en cada iteración se ha añadido la arista de menor costo.
Para el algoritmo de Prim, considerar la siguiente notación:
Sea

V el conjunto de vértices de G
U elsubconjunto de V. Su valor inicial es el primer vértice de V. Es decir, U={1}
L es una lista de aristas que se va formando con las aristas de menor costo que se van
seleccionando. Para inicial, Lestá vacía (L=Ø).

ALGORITMO:
Mientras (V≠U) repetir
Elegir una arista (u,v) Є A(G) mínima, siendo u Є U y v Є (V-U)
Agregar la arista (u,v) a L
Agregar el nodo v a U

A continuación sepresenta la corrida del algoritmo con el grafo dado y sus respectivos estados:

2

3
A1

A1

1
2

2

3

1
2

2
5

4

k
1
2
3
4

U
{1}
{1,4}
{1,4,2}
{1,4,2,5}

(u,v)...