Algoritmos y Estructuras de Datos (VJ1215)

#include <limits> // infinity
#include "ColaDePrioridad.h"

vector<int> GrafoNoDirigido::arbolDeRecubrimientoOptimo() const { // Algoritmo de Prim
                                                                  // Suponemos grafo conexo
   int cantidadDeVertices = vertices.size();
					       
   ColaDePrioridad colaDePrioridad(cantidadDeVertices);

   vector<float> pesoCaminoOptimo(cantidadDeVertices, numeric_limits<float>::infinity());
   vector<int> padre(cantidadDeVertices, -1);
   vector<bool> estaEnLaColaDePrioridad(cantidadDeVertices, true);

   pesoCaminoOptimo[0] = 0;
   padre[0] = -2;

   for (int v = 0; v < cantidadDeVertices; v++)
      colaDePrioridad.insertar(v, pesoCaminoOptimo[v]);

   while (! colaDePrioridad.estaVacia()) {
      int elegido = colaDePrioridad.eliminarMinimo();
      estaEnLaColaDePrioridad[elegido] = false;
      for (Arco * arco = vertices[elegido].primerArco; arco != nullptr; arco = arco->siguiente) {
	 int vecino = arco->vecino;
	 if (estaEnLaColaDePrioridad[vecino]) {
	    float nuevoPeso = arco->peso;
	    if (nuevoPeso < pesoCaminoOptimo[vecino]) {
	       pesoCaminoOptimo[vecino] = nuevoPeso;
	       padre[vecino] = elegido;
	       colaDePrioridad.cambiarPrioridad(vecino, nuevoPeso);
	    }
	 }
      }
   }

   return padre;

}
      

Comparando esta implementación con la solución del ejercicio 12 (algoritmo de Dijkstra), podemos observar 3 diferencias:

1. En el algoritmo de Dijkstra, el vértice origen es un dato de entrada. En el algoritmo de Prim, podemos elegir un vértice origen cualquiera (por ejemplo, el 0).

2. En el algoritmo de Prim, la implementación no se puede simplificar eliminando la instrucción que comprueba si el vecino está todavía en la cola de prioridad.

3. En el algoritmo de Dijkstra, los pesos de los arcos se van sumando para obtener los pesos de los caminos; en el algoritmo de Prim, los pesos de los arcos no se suman.