TEORIA DE GRAFOS ALGORITMOS PRINCIPALES
MARIO DUSTANO CONTRERAS CASTRO
TEORIA DE GRAFOS ALGORITMO DE PRIM
El algoritmo de Prim es un algoritmo perteneciente a la teoría de los grafos para encontrar un árbol recubridor mínimo en un grafo conexo, no dirigido y cuyas aristas están etiquetadas
El algoritmo encuentra un subconjunto de aristas que forman un árbol con todos los vértices, donde el peso total de todas las aristas en el árbol es el mínimo posible. Si el grafo no es conexo, entonces el algoritmo encontrará el árbol recubridor mínimo para uno de los componentes conexos que forman dicho grafo no conexo (sin crear ciclo).
El algoritmo incrementa continuamente el tamaño de un árbol, comenzando por un vértice inicial al que se le van agregando sucesivamente vértices cuya distancia a los anteriores es mínima. Esto significa que en cada paso, las aristas a considerar son aquellas que inciden en vértices que ya pertenecen al árbol.
Pseudocódigo del algoritmo
Estructura de datos auxiliar: Cola = Estructura de datos Cola de prioridad
Prim (Grafo G)
// Inicializamos todos los nodos del grafo. La distancia la ponemos a infinito y el padre de cada nodo a NULL
// Se adiciona, en una cola de prioridad donde la prioridad es la distancia, todas las parejas <nodo,distancia> del grafo por cada u en V[G] hacer
distancia[u] = INFINITO
padre[u] = NULL
Añadir(cola,<u,distancia[u]>)
distancia[u]=0
mientras !esta_vacia(cola) hacer
// OJO: Se entiende por mayor prioridad aquel nodo cuya distancia[u] es menor.
u = extraer_minimo(cola) //devuelve el mínimo y lo elimina de la cola.
por cada v adyacente a 'u' hacer
si ((v ∈ cola) && (distancia[v] > peso(u, v)) entonces
padre[v] = u
distancia[v] = peso(u, v)
Actualizar(cola,<v,distancia[v]
ALGORITMO PRIM
mariocontreras
Created on June 29, 2021
TEORIA DE GRAFOS
Start designing with a free template
Discover more than 1500 professional designs like these:
View
Practical Video
View
Akihabara Video
View
Essential Video
View
Space video
View
Season's Greetings Video Mobile
View
End of the Year Wrap Up
View
Christmas Promotion Video
Explore all templates
Transcript
TEORIA DE GRAFOS ALGORITMOS PRINCIPALES
MARIO DUSTANO CONTRERAS CASTRO
TEORIA DE GRAFOS ALGORITMO DE PRIM
El algoritmo de Prim es un algoritmo perteneciente a la teoría de los grafos para encontrar un árbol recubridor mínimo en un grafo conexo, no dirigido y cuyas aristas están etiquetadas
El algoritmo encuentra un subconjunto de aristas que forman un árbol con todos los vértices, donde el peso total de todas las aristas en el árbol es el mínimo posible. Si el grafo no es conexo, entonces el algoritmo encontrará el árbol recubridor mínimo para uno de los componentes conexos que forman dicho grafo no conexo (sin crear ciclo).
El algoritmo incrementa continuamente el tamaño de un árbol, comenzando por un vértice inicial al que se le van agregando sucesivamente vértices cuya distancia a los anteriores es mínima. Esto significa que en cada paso, las aristas a considerar son aquellas que inciden en vértices que ya pertenecen al árbol.
Pseudocódigo del algoritmo Estructura de datos auxiliar: Cola = Estructura de datos Cola de prioridad Prim (Grafo G) // Inicializamos todos los nodos del grafo. La distancia la ponemos a infinito y el padre de cada nodo a NULL // Se adiciona, en una cola de prioridad donde la prioridad es la distancia, todas las parejas <nodo,distancia> del grafo por cada u en V[G] hacer distancia[u] = INFINITO padre[u] = NULL Añadir(cola,<u,distancia[u]>) distancia[u]=0 mientras !esta_vacia(cola) hacer // OJO: Se entiende por mayor prioridad aquel nodo cuya distancia[u] es menor. u = extraer_minimo(cola) //devuelve el mínimo y lo elimina de la cola. por cada v adyacente a 'u' hacer si ((v ∈ cola) && (distancia[v] > peso(u, v)) entonces padre[v] = u distancia[v] = peso(u, v) Actualizar(cola,<v,distancia[v]