Universidad Iberoamericana, Biblioteca Francisco Xavier Clavigero,

¿Cómo cito la información que encontré en

Internet? Algunos lineamientos para asentar una bibliografía.

http://biblion.bib.uia.mx/internet/citas.htm

(21 agosto 01) 

http://weierstrass.is.tokushima-u.ac.jp/ikeda/suuri/dijkstra/PrimApp.shtml?demo6

Debido a la simplicidad que este algoritmo conlleva puede ser
http://www.algovidea.cl/index.php?view=article&catid=39%3Acoberturaminima&id=53%3Acoberturaminima&format=pdf&option=com_content&Itemid=63

There is a new map showing mathematicians' birthplaces:
There are 29 new biographies.http://www-history.mcs.st-and.ac.uk/Biographies/Jarnik.html

Robert C. Prim
En 1941 se licenció en ingeniería eléctrica en la Universidad de Princeton. Más tarde, en 1949 recibe su doctorado en matemáticas en la misma universidad. Trabajó en dicha universidad desde 1948 hasta 1949 como investigador asociado.

http://wikitechnology0.blogspot.com/2012/10/biografia-de-robert-c-prim.html

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.
http://es.wikipedia.org/wiki/Algoritmo_de_Prim

http://www.cenatav.co.cu/doc/RTecnicos/RT%20SerieAzul_049web.pdf 

Pseudocó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

     para cada u perteneciente a V[G] hacer

         distancia[u] = INFINITO;

         padre[u] = NULL;

         distancia[s]= 0;

//colocamos todos los nodos del grafo 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 prioridad

     mientras cola != 0 hacer

        u = extraer_minimo(cola);

        para v perteneciente adyacencia[u] hacer

          si ((v pertenece a cola) && (distancia[v]> peso(u, v)) hacer

                   padre[v] = u;

                   distancia[v] = peso(u, v);

                   actualizar(cola,v);

Siguiendo el algoritmo de Prim, se tiene:
- Se elige por ejemplo, el nodo 1 y se marca.
- Se elige la arista con menor valor incidente en 1, la (1, 3) = 1 se marca y se
marca el otro nodo en el que incide, el 3.
- Se elige la arista con menor valor incidente en un nodo marcado y otro que
no lo esté, la (1, 2) = 3 se marca y se marca el nodo no marcado, el 2.
- Se elige la arista con menor valor incidente en un nodo marcado y otro que
no lo esté, la (2, 5) = 5 se marca y se marca el nodo no marcado, el 5.
- Se elige la arista con menor valor incidente en un nodo marcado y otro que
no lo esté, la (5, 6) = 1  se marca y se marca el nodo no marcado, el 6.
- Se elige la arista con menor valor incidente en un nodo marcado y otro que
no lo esté, la (5, 7) = 2 se marca y se marca el nodo no marcado, el 7.
- Se elige la arista con menor valor incidente en un nodo marcado y otro que
no lo esté, la (5, 4) = 6 se marca y se marca el nodo no marcado, el 4.
- FIN. Se finaliza dado que se tiene marcados los 7 nodos del grafo.
- Por tanto el árbol de mínima expansión resultante sería:



Código en Java

 public class Algorithms
{
    public static Graph PrimsAlgorithm (Graph g, int s)
    {
 int n = g.getNumberOfVertices ();
 Entry[] table = new Entry [n];
 for (int v = 0; v < n; ++v)
     table [v] = new Entry ();
 table [s].distance = 0;
 PriorityQueue queue =
     new BinaryHeap (g.getNumberOfEdges());
 queue.enqueue (
     new Association (new Int (0), g.getVertex (s)));
 while (!queue.isEmpty ())
 {
     Association assoc = (Association) queue.dequeueMin();
     Vertex v0 = (Vertex) assoc.getValue ();
     int n0 = v0.getNumber ();
     if (!table [n0].known)
     {
  table [n0].known = true;
  Enumeration p = v0.getEmanatingEdges ();
  while (p.hasMoreElements ())
  {
      Edge edge = (Edge) p.nextElement ();
      Vertex v1 = edge.getMate (v0);
      int n1 = v1.getNumber ();


 Int wt = (Int) edge.getWeight ();
      int d = wt.intValue ();
      if (!table[n1].known && table[n1].distance>d)
      {   table [n1].distance = d;
   table [n1].predecessor = n0;
   queue.enqueue (
       new Association (new Int (d), v1));
      }
  }
     }
 }
 Graph result = new GraphAsLists (n);
 for (int v = 0; v < n; ++v)
     result.addVertex (v);
 for (int v = 0; v < n; ++v)
     if (v != s)
  result.addEdge (v, table [v].predecessor);
 return result;
    }
}   
Mas del algoritmo