BFS - Breadth First Search

Es un algoritmo para recorrer elementos en un grafo, intuitivamente, se comienza en la raíz (eligiendo algún nodo como elemento raíz en el caso de un grafo) y se exploran todos los vecinos de este nodo.
A continuación para cada uno de los vecinos se exploran sus respectivos vecinos adyacentes, y así hasta que se recorra todo el árbol.

Formalmente, BFS es un algoritmo de búsqueda sin información, que expande y examina todos los nodos de un árbol sistemáticamente para buscar una solución.
El algoritmo no usa ninguna estrategia heurística.


En español:

Dado un vértice de inicio, tomo la lista de sus adyacentes y los recorro, antes de entrar en profundidad de los adyacentes de éstos.

Finalizado el nivel, entro a recorrer mis nuevos adyacentes no visitados aún (que son adyacentes de uno de los adyacentes del nodo inicial).

Pseudo-código:

  BFS(grafo G, nodo_fuente s)
{
   // recorremos todos los vértices del grafo inicializándolos a NO_VISITADO,
   // distancia INFINITA y padre de cada nodo NULL
   for u ∈ V[G] do
   {
      estado[u] = NO_VISITADO;
      distancia[u] = INFINITO; /* distancia infinita si el nodo no es alcanzable */
      padre[u] = NULL;
   }
   estado[s] = VISITADO;
   distancia[s] = 0;
   Encolar(Q, s);
   while !vacia(Q) do
   {
      // extraemos el nodo u de la cola Q y exploramos todos sus nodos adyacentes
      u = extraer(Q);
      for  v ∈ adyacencia[u]  do
      {
         if estado[v] == NO_VISITADO then
         {
              estado[v] = VISITADO;
              distancia[v] = distancia[u] + 1;
              padre[v] = u;
              Encolar(Q, v);
         }
      }
   }
}

El tiempo de ejecución es O(|V|+|E|). Nótese que cada nodo es puesto a la cola una vez y su lista de adyacencia es recorrida una vez también.

Fuente: wikipedia

Algoritmo de Prim

El algoritmo de Prim

Es un algoritmo de 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.

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 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.


Pseudo-código

PRIM (Grafo G, nodo_fuente s)
     // inicializamos todos los nodos del grafo. La distancia la ponemos a infinito
     // y el padre de cada nodo a NULL
      for each u ∈ V[G] do
          distancia[u] = INFINITO
          padre[u] = NULL
      distancia[s]=0
      //encolamos todos los nodos del grafo
      Encolar(cola, V[G])
      while cola != 0 do
          // OJO: Se extrae el nodo que tiene distancia mínima y se conserva la condición 
          // de Cola de prioridad
          u = extraer_minimo(cola)
          for v ∈ adyacencia[u] do
              if ((v ∈ cola) && (distancia[v] > peso(u, v)) do
                  padre[v] = u
                  distancia[v] = peso(u, v)

En español:

• Como debemos tener un vértice de partida, tomamos este vértice y armamos una lista con las aristas de sus adyacentes.
  Esa lista la confeccionamos en orden descendiente según su costo.
• Tomamos la arista de menor costo (siempre y cuando, al agregar esta arista, no generemos un ciclo) y la agregamos a nuestro árbol.
• Para el siguiente paso, vamos a tener que utilizar el vértice que acabamos de colocar, agregamos las aristas adyacentes de éste de la misma manera que lo hicimos anteriormente.
• Y así sucesivamente hasta tener todos los vértices del grafo, dentro del A.C.C.M.

fuente: wikipedia (pseudo-código) y apuntes mios