Algoritmos De Busqueda

Algoritmo Cobertura Mínima

 

Algoritmo   Los algoritmos que pueden dar solución a este problema son: - Algoritmo de Dijkstra - Algoritmo de Kruskal - Algoritmo de Prim  En este artículotrataremos el algoritmo de Prim como forma de solución para la cobertura minima, debido a la simplicidad que este algoritmo conlleva puede ser aprovechado sin necesidad de ser un gran experto enprogramación.   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 porDijkstra en 1959. Por esta razón, el algoritmo es también conocido como algoritmo DJP o algoritmo de Jarnik.Consiste en un algoritmo de la teoría de los grafos para encontrar un árbol de cobertura mínimoen un grafo conexo (grafo que  para cada par de nodos está conectado por un camino, o sea, si para cualquier par de nodos A y B, existe al menos un camino posible desde B hacia A), no dirigido y cuyasaristas están etiquetadas. En otras palabras, 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 elmí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 (grafo donde hay nodos que nopueden ser conectados por medio de un camino).  

1/6

Algoritmo Cobertura Mínima

Pseudocódigo

PRIM (Grafo G, nodo_fuente s)       // Inicializamos todos los nodos del grafo. La distancia laponemos a infinito y el padre de      para cada u perteneciente a V[G] hacer          distancia[u] = INFINITO;          padre[u] = NULL;          distancia[s]= 0;

//colocamos todos los nodos delgrafo V, en una cola      PonerenCola(cola, V[G]);

// Se extrae el nodo que tiene distancia mínima y se conserva la condición de cola de prio

     mientras cola != 0 hacer         u =...