Scribd
Cargar
204 vistas2 páginas

Algoritmo de Prim: Árbol Recubridor Mínimo

El algoritmo de Prim encuentra un árbol recubridor mínimo en un grafo conexo no dirigido mediante la selección sucesiva de las aristas de menor peso entre nodos marcados y no marcados. Comienza marcando un nodo y luego marca el nodo adyacente no marcado conectado por la arista de menor peso, repitiendo este proceso hasta marcar todos los nodos. Se usa comúnmente para implementar redes de cables y postes.

Cargado por

byron guerrero
Derechos de autor
© All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como DOC, PDF, TXT o lee en línea desde Scribd
204 vistas2 páginas

Algoritmo de Prim: Árbol Recubridor Mínimo

El algoritmo de Prim encuentra un árbol recubridor mínimo en un grafo conexo no dirigido mediante la selección sucesiva de las aristas de menor peso entre nodos marcados y no marcados. Comienza marcando un nodo y luego marca el nodo adyacente no marcado conectado por la arista de menor peso, repitiendo este proceso hasta marcar todos los nodos. Se usa comúnmente para implementar redes de cables y postes.

Cargado por

byron guerrero
Derechos de autor
© All Rights Reserved
Nos tomamos en serio los derechos de los contenidos. Si sospechas que se trata de tu contenido, reclámalo aquí.
Formatos disponibles
Descarga como DOC, PDF, TXT o lee en línea desde Scribd

ALGORITMO DE PRIM

El algoritmo fue diseñado en 1930 por el matemático Vojtech Jarnik y luego de manera
independiente por el científico computacional Robert C. Prim en 1957 y redescubierto por Dijkstra
en 1959. Por esta razón, el algoritmo es también conocido como algoritmo DJP o algoritmo de
Jarnik.

El algoritmo de Prim es un Algoritmo perteneciente a la teoría de grafos para encontrar un Arbol


Recubridor Minimo (ARM) en un grafo conexo (si existe un camino entre cualquier par de vértices),
no dirigido y cuyas aristas están etiquetadas.

Simplemente es que lo que representa es un subgrafo que contiene todos los nodos de G,
conectados con el menor valor posible entre ellos

PASOS PARA REALIZAR EL ALGORITMO:


1. Se Marca un nodo cualquiera, el cual será el nodo de partida
2. Se selecciona la arista de menor valor incidente en el nodo marcado anteriormente, y
marcamos el otro nodo en el que incide
3. Se repite el paso 2, siempre y cuando la arista elegida enlace un nodo marcado y otro que
no lo este.
4. El proceso termina cuando tenemos todos los nodos del grafo marcados.

Ejemplo: Determinar el Arbol Recubridor Minimo del siguiente grafo


Siguiendo el algoritmo de Prim, tenemos:

Elegimos, por ejemplo, el nodo A como nodo de partida y lo marcamos.


Marcamos el nodo B, ya que la arista que une el nodo (A,B) es la arista de menor valor
que une un nodo marcado y otro que no lo esta.
Marcamos el nodo C, ya que la arista que une el nodo (A,C) es la arista de menor valor
que une un nodo marcado y otro que no lo esta.
Marcamos el nodo G, ya que la arista que une el nodo C y el nodo G, es la arista de
menor valor que une un nodo marcado y otro que no lo esta
Marcamos el nodo F, ya que la arista que no el nodo G y el nodo F, es la arista de
menor valor que une un nodo marcado y otro que no lo esta.
Marcamos el nodo E, ya que la arista que uno el nodo G y el nodo E, es la arista de
menor valor que une un nodo marcado y otro que no lo esta.
Marcamos el nodo D, ya que la arista que une el nodo D y el nodo G, es la arista de
menor valor que une un nodo marcado y otro que no lo esta.
FIN. Finalizamos dado que tenemos marcados los 7 nodos del grafo.
Por tanto el árbol de mínima expansión resultante sería:

Su aplicación mas común es la implementación de cables de redes, de servidores, de


postes de luz, entre otros.

[Link]

[Link]

También podría gustarte